home *** CD-ROM | disk | FTP | other *** search
/ QRZ! Ham Radio 8 / QRZ Ham Radio Callsign Database - Volume 8.iso / mac / files / dsp / dspkgctr.z / dspkgctr / gcc / cse.c < prev    next >
C/C++ Source or Header  |  1992-06-08  |  116KB  |  3,980 lines
  1. /* Common subexpression elimination for GNU compiler.
  2.    Copyright (C) 1987, 1988, 1989 Free Software Foundation, Inc.
  3.  
  4.    $Id: cse.c,v 1.9 92/02/21 15:23:10 pete Exp $
  5.  
  6. This file is part of GNU CC.
  7.  
  8. GNU CC is free software; you can redistribute it and/or modify
  9. it under the terms of the GNU General Public License as published by
  10. the Free Software Foundation; either version 1, or (at your option)
  11. any later version.
  12.  
  13. GNU CC is distributed in the hope that it will be useful,
  14. but WITHOUT ANY WARRANTY; without even the implied warranty of
  15. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16. GNU General Public License for more details.
  17.  
  18. You should have received a copy of the GNU General Public License
  19. along with GNU CC; see the file COPYING.  If not, write to
  20. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  21.  
  22.  
  23. #include "config.h"
  24. #include "rtl.h"
  25. #include "regs.h"
  26. #if ! defined( _INTELC32_ )
  27. #include "hard-reg-set.h"
  28. #else
  29. #include "hardrset.h"
  30. #endif
  31. #include "flags.h"
  32. #include "real.h"
  33.  
  34. #include <setjmp.h>
  35.  
  36. /* The basic idea of common subexpression elimination is to go
  37.    through the code, keeping a record of expressions that would
  38.    have the same value at the current scan point, and replacing
  39.    expressions encountered with the cheapest equivalent expression.
  40.  
  41.    It is too complicated to keep track of the different possibilities
  42.    when control paths merge; so, at each label, we forget all that is
  43.    known and start fresh.  This can be described as processing each
  44.    basic block separately.  Note, however, that these are not quite
  45.    the same as the basic blocks found by a later pass and used for
  46.    data flow analysis and register packing.  We do not need to start fresh
  47.    after a conditional jump instruction if there is no label there.
  48.  
  49.    We use two data structures to record the equivalent expressions:
  50.    a hash table for most expressions, and several vectors together
  51.    with "quantity numbers" to record equivalent (pseudo) registers.
  52.  
  53.    The use of the special data structure for registers is desirable
  54.    because it is faster.  It is possible because registers references
  55.    contain a fairly small number, the register number, taken from
  56.    a contiguously allocated series, and two register references are
  57.    identical if they have the same number.  General expressions
  58.    do not have any such thing, so the only way to retrieve the
  59.    information recorded on an expression other than a register
  60.    is to keep it in a hash table.
  61.  
  62. Registers and "quantity numbers":
  63.    
  64.    At the start of each basic block, all of the (hardware and pseudo)
  65.    registers used in the function are given distinct quantity
  66.    numbers to indicate their contents.  During scan, when the code
  67.    copies one register into another, we copy the quantity number.
  68.    When a register is loaded in any other way, we allocate a new
  69.    quantity number to describe the value generated by this operation.
  70.    `reg_qty' records what quantity a register is currently thought
  71.    of as containing.
  72.  
  73.    We also maintain a bidirectional chain of registers for each
  74.    quantity number.  `qty_first_reg', `qty_last_reg',
  75.    `reg_next_eqv' and `reg_prev_eqv' hold these chains.
  76.  
  77.    The first register in a chain is the one whose lifespan is least local.
  78.    Among equals, it is the one that was seen first.
  79.    We replace any equivalent register with that one.
  80.  
  81. Constants and quantity numbers
  82.  
  83.    When a quantity has a known constant value, that value is stored
  84.    in the appropriate element of qty_const.  This is in addition to
  85.    putting the constant in the hash table as is usual for non-regs.
  86.  
  87.    Regs are preferred to constants as they are to everything else,
  88.    but expressions containing constants can be simplified, by fold_rtx.
  89.  
  90.    When a quantity has a known nearly constant value (such as an address
  91.    of a stack slot), that value is stored in the appropriate element
  92.    of qty_const.
  93.  
  94.    Integer constants don't have a machine mode.  However, cse
  95.    determines the intended machine mode from the destination
  96.    of the instruction that moves the constant.  The machine mode
  97.    is recorded in the hash table along with the actual RTL
  98.    constant expression so that different modes are kept separate.
  99.  
  100. Other expressions:
  101.  
  102.    To record known equivalences among expressions in general
  103.    we use a hash table called `table'.  It has a fixed number of buckets
  104.    that contain chains of `struct table_elt' elements for expressions.
  105.    These chains connect the elements whose expressions have the same
  106.    hash codes.
  107.  
  108.    Other chains through the same elements connect the elements which
  109.    currently have equivalent values.
  110.  
  111.    Register references in an expression are canonicalized before hashing
  112.    the expression.  This is done using `reg_qty' and `qty_first_reg'.
  113.    The hash code of a register reference is computed using the quantity
  114.    number, not the register number.
  115.  
  116.    When the value of an expression changes, it is necessary to remove from the
  117.    hash table not just that expression but all expressions whose values
  118.    could be different as a result.
  119.  
  120.      1. If the value changing is in memory, except in special cases
  121.      ANYTHING referring to memory could be changed.  That is because
  122.      nobody knows where a pointer does not point.
  123.      The function `invalidate_memory' removes what is necessary.
  124.  
  125.      The special cases are when the address is constant or is
  126.      a constant plus a fixed register such as the frame pointer
  127.      or a static chain pointer.  When such addresses are stored in,
  128.      we can tell exactly which other such addresses must be invalidated
  129.      due to overlap.  `invalidate' does this.
  130.      All expressions that refer to non-constant
  131.      memory addresses are also invalidated.  `invalidate_memory' does this.
  132.  
  133.      2. If the value changing is a register, all expressions
  134.      containing references to that register, and only those,
  135.      must be removed.
  136.  
  137.    Because searching the entire hash table for expressions that contain
  138.    a register is very slow, we try to figure out when it isn't necessary.
  139.    Precisely, this is necessary only when expressions have been
  140.    entered in the hash table using this register, and then the value has
  141.    changed, and then another expression wants to be added to refer to
  142.    the register's new value.  This sequence of circumstances is rare
  143.    within any one basic block.
  144.  
  145.    The vectors `reg_tick' and `reg_in_table' are used to detect this case.
  146.    reg_tick[i] is incremented whenever a value is stored in register i.
  147.    reg_in_table[i] holds -1 if no references to register i have been
  148.    entered in the table; otherwise, it contains the value reg_tick[i] had
  149.    when the references were entered.  If we want to enter a reference
  150.    and reg_in_table[i] != reg_tick[i], we must scan and remove old references.
  151.    Until we want to enter a new entry, the mere fact that the two vectors
  152.    don't match makes the entries be ignored if anyone tries to match them.
  153.  
  154.    Registers themselves are entered in the hash table as well as in
  155.    the equivalent-register chains.  However, the vectors `reg_tick'
  156.    and `reg_in_table' do not apply to expressions which are simple
  157.    register references.  These expressions are removed from the table
  158.    immediately when they become invalid, and this can be done even if
  159.    we do not immediately search for all the expressions that refer to
  160.    the register.
  161.  
  162.    A CLOBBER rtx in an instruction invalidates its operand for further
  163.    reuse.  A CLOBBER or SET rtx whose operand is a MEM:BLK
  164.    invalidates everything that resides in memory.
  165.  
  166. Related expressions:
  167.  
  168.    Constant expressions that differ only by an additive integer
  169.    are called related.  When a constant expression is put in
  170.    the table, the related expression with no constant term
  171.    is also entered.  These are made to point at each other
  172.    so that it is possible to find out if there exists any
  173.    register equivalent to an expression related to a given expression.  */
  174.    
  175. /* One plus largest register number used in this function.  */
  176.  
  177. static int max_reg;
  178.  
  179. /* Length of vectors indexed by quantity number.
  180.    We know in advance we will not need a quantity number this big.  */
  181.  
  182. static int max_qty;
  183.  
  184. /* Next quantity number to be allocated.
  185.    This is 1 + the largest number needed so far.  */
  186.  
  187. static int next_qty;
  188.  
  189. /* Indexed by quantity number, gives the first (or last) (pseudo) register 
  190.    in the chain of registers that currently contain this quantity.  */
  191.  
  192. static int *qty_first_reg;
  193. static int *qty_last_reg;
  194.  
  195. /* Indexed by quantity number, gives the rtx of the constant value of the
  196.    quantity, or zero if it does not have a known value.
  197.    A sum of the frame pointer (or arg pointer) plus a constant
  198.    can also be entered here.  */
  199.  
  200. static rtx *qty_const;
  201.  
  202. /* Indexed by qty number, gives the insn that stored the constant value
  203.    recorded in `qty_const'.  */
  204.  
  205. static rtx *qty_const_insn;
  206.  
  207. /* Value stored in CC0 by previous insn:
  208.    0 if previous insn didn't store in CC0.
  209.    else 0100 + (M&7)<<3 + (N&7)
  210.    where M is 1, 0 or -1 if result was >, == or < as signed number
  211.    and N is 1, 0 or -1 if result was >, == or < as unsigned number.
  212.    0200 bit may also be set, meaning that only == and != comparisons
  213.    have known results.  */
  214.  
  215. static int prev_insn_cc0;
  216.  
  217. /* For machines where CC0 is one bit, we may see CC0 assigned a
  218.    constant value (after fold_rtx).
  219.    Record here the value stored in the previous insn (0 if none).  */
  220.  
  221. static rtx prev_insn_explicit_cc0;
  222.  
  223. /* Previous actual insn.  0 if at first insn of basic block.  */
  224.  
  225. static rtx prev_insn;
  226.  
  227. /* Insn being scanned.  */
  228.  
  229. static rtx this_insn;
  230.  
  231. /* Index by (pseudo) register number, gives the quantity number
  232.    of the register's current contents.  */
  233.  
  234. static int *reg_qty;
  235.  
  236. /* Index by (pseudo) register number, gives the number of the next
  237.    (pseudo) register in the chain of registers sharing the same value.
  238.    Or -1 if this register is at the end of the chain.  */
  239.  
  240. static int *reg_next_eqv;
  241.  
  242. /* Index by (pseudo) register number, gives the number of the previous
  243.    (pseudo) register in the chain of registers sharing the same value.
  244.    Or -1 if this register is at the beginning of the chain.  */
  245.  
  246. static int *reg_prev_eqv;
  247.  
  248. /* Index by (pseudo) register number, gives the latest rtx
  249.    to use to insert a ref to that register.  */
  250.  
  251. static rtx *reg_rtx;
  252.  
  253. /* Index by (pseudo) register number, gives the number of times
  254.    that register has been altered in the current basic block.  */
  255.  
  256. static int *reg_tick;
  257.  
  258. /* Index by (pseudo) register number, gives the reg_tick value at which
  259.    rtx's containing this register are valid in the hash table.
  260.    If this does not equal the current reg_tick value, such expressions
  261.    existing in the hash table are invalid.
  262.    If this is -1, no expressions containing this register have been
  263.    entered in the table.  */
  264.  
  265. static int *reg_in_table;
  266.  
  267. /* Two vectors of max_reg ints:
  268.    one containing all -1's; in the other, element i contains i.
  269.    These are used to initialize various other vectors fast.  */
  270.  
  271. static int *all_minus_one;
  272. static int *consec_ints;
  273.  
  274. /* Set nonzero in cse_insn to tell cse_basic_block to skip immediately
  275.    to the next basic block and treat it as a continuation of this one.  */
  276.  
  277. static int cse_skip_to_next_block;
  278.  
  279. /* CUID of insn that starts the basic block currently being cse-processed.  */
  280.  
  281. static int cse_basic_block_start;
  282.  
  283. /* CUID of insn that ends the basic block currently being cse-processed.  */
  284.  
  285. static int cse_basic_block_end;
  286.  
  287. /* Vector mapping INSN_UIDs to cuids.
  288.    The cuids are like uids but increase monononically always.
  289.    We use them to see whether a reg is used outside a given basic block.  */
  290.  
  291. static short *uid_cuid;
  292.  
  293. /* Get the cuid of an insn.  */
  294.  
  295. #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
  296.  
  297. /* Nonzero if cse has altered conditional jump insns
  298.    in such a way that jump optimization should be redone.  */
  299.  
  300. static int cse_jumps_altered;
  301.  
  302. /* canon_hash stores 1 in do_not_record
  303.    if it notices a reference to CC0, CC1 or PC.  */
  304.  
  305. static int do_not_record;
  306.  
  307. /* canon_hash stores 1 in hash_arg_in_memory
  308.    if it notices a reference to memory within the expression being hashed.  */
  309.  
  310. static int hash_arg_in_memory;
  311.  
  312. /* canon_hash stores 1 in hash_arg_in_struct
  313.    if it notices a reference to memory that's part of a structure.  */
  314.  
  315. static int hash_arg_in_struct;
  316.  
  317. /* The hash table contains buckets which are chains of `struct table_elt's,
  318.    each recording one expression's information.
  319.    That expression is in the `exp' field.
  320.  
  321.    Those elements with the same hash code are chained in both directions
  322.    through the `next_same_hash' and `prev_same_hash' fields.
  323.  
  324.    Each set of expressions with equivalent values
  325.    are on a two-way chain through the `next_same_value'
  326.    and `prev_same_value' fields, and all point with
  327.    the `first_same_value' field at the first element in
  328.    that chain.  The chain is in order of increasing cost.
  329.    Each element's cost value is in its `cost' field.
  330.  
  331.    The `in_memory' field is nonzero for elements that
  332.    involve any reference to memory.  These elements are removed
  333.    whenever a write is done to an unidentified location in memory.
  334.    To be safe, we assume that a memory address is unidentified unless
  335.    the address is either a symbol constant or a constant plus
  336.    the frame pointer or argument pointer.
  337.  
  338.    The `in_struct' field is nonzero for elements that
  339.    involve any reference to memory inside a structure or array.
  340.  
  341.    The `equivalence_only' field means that this expression came from a
  342.    REG_EQUIV or REG_EQUAL note; it is not valid for substitution into an insn.
  343.  
  344.    The `related_value' field is used to connect related expressions
  345.    (that differ by adding an integer).
  346.    The related expressions are chained in a circular fashion.
  347.    `related_value' is zero for expressions for which this
  348.    chain is not useful.
  349.  
  350.    The `mode' field is usually the same as GET_MODE (`exp'), but
  351.    if `exp' is a CONST_INT and has no machine mode then the `mode'
  352.    field is the mode it was being used as.  Each constant is
  353.    recorded separately for each mode it is used with.  */
  354.  
  355.  
  356. struct table_elt
  357. {
  358.   rtx exp;
  359.   struct table_elt *next_same_hash;
  360.   struct table_elt *prev_same_hash;
  361.   struct table_elt *next_same_value;
  362.   struct table_elt *prev_same_value;
  363.   struct table_elt *first_same_value;
  364.   struct table_elt *related_value;
  365.   int cost;
  366.   enum machine_mode mode;
  367.   char in_memory;
  368.   char in_struct;
  369.   char equivalence_only;
  370. };
  371.  
  372. #define HASH(x, m) (canon_hash (x, m) % NBUCKETS)
  373. /* We don't want a lot of buckets, because we rarely have very many
  374.    things stored in the hash table, and a lot of buckets slows
  375.    down a lot of loops that happen frequently.  */
  376. #define NBUCKETS 31
  377.  
  378. static struct table_elt *table[NBUCKETS];
  379.  
  380. /* Chain of `struct table_elt's made so far for this function
  381.    but currently removed from the table.  */
  382.  
  383. static struct table_elt *free_element_chain;
  384.  
  385. /* Number of `struct table_elt' structures made so far for this function.  */
  386.  
  387. static int n_elements_made;
  388.  
  389. /* Maximum value `n_elements_made' has had so far in this compilation
  390.    for functions previously processed.  */
  391.  
  392. static int max_elements_made;
  393.  
  394. /* Bits describing what kind of values in memory must be invalidated
  395.    for a particular instruction.  If all three bits are zero,
  396.    no memory refs need to be invalidated.  Each bit is more powerful
  397.    than the preceding ones, and if a bit is set then the preceding
  398.    bits are also set.
  399.  
  400.    Here is how the bits are set.
  401.    Writing at a fixed address invalidates only variable addresses,
  402.    writing in a structure element at variable address
  403.      invalidates all but scalar variables,
  404.    and writing in anything else at variable address invalidates everything.  */
  405.  
  406. struct write_data
  407. {
  408.   int var : 1;            /* Invalidate variable addresses.  */
  409.   int nonscalar : 1;        /* Invalidate all but scalar variables.  */
  410.   int all : 1;            /* Invalidate all memory refs.  */
  411. };
  412.  
  413. /* Nonzero if X has the form (PLUS frame-pointer integer).  */
  414.  
  415. #define FIXED_BASE_PLUS_P(X)                    \
  416.   (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT    \
  417.    && (XEXP (X, 0) == frame_pointer_rtx || XEXP (X, 0) == arg_pointer_rtx))
  418.  
  419. #if defined( _MSDOS )
  420. void warning ( char * s, ... );
  421. #endif
  422.  
  423. static struct table_elt *lookup ();
  424. static void free_element ();
  425.  
  426. static void remove_invalid_refs ();
  427. static int exp_equiv_p ();
  428. int refers_to_p ();
  429. int refers_to_mem_p ();
  430. static void invalidate_from_clobbers ();
  431. static int safe_hash ();
  432. static int canon_hash ();
  433. static rtx equiv_constant ();
  434. static int get_integer_term ();
  435. static rtx get_related_value ();
  436. static void note_mem_written ();
  437. static int cse_rtx_addr_varies_p ();
  438. static int fold_cc0 ();
  439.  
  440. /* Return an estimate of the cost of computing rtx X.
  441.    The only use of this is to compare the costs of two expressions
  442.    to decide whether to replace one with the other.  */
  443.  
  444. static int
  445. rtx_cost (x)
  446.      rtx x;
  447. {
  448.   register int i, j;
  449.   register enum rtx_code code;
  450.   register char *fmt;
  451.   register int total;
  452.  
  453.   if (x == 0)
  454.     return 0;
  455.  
  456.   code = GET_CODE (x);
  457.   switch (code)
  458.     {
  459.     case REG:
  460.       return 1;
  461.     case SUBREG:
  462.       return 2;
  463.     CONST_COSTS (x, code);
  464.     }
  465.  
  466.   total = 2;
  467.  
  468.   /* Sum the costs of the sub-rtx's, plus 2 just put in.  */
  469.  
  470.   fmt = GET_RTX_FORMAT (code);
  471.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  472.     if (fmt[i] == 'e')
  473.       total += rtx_cost (XEXP (x, i));
  474.     else if (fmt[i] == 'E')
  475.       for (j = 0; j < XVECLEN (x, i); j++)
  476.     total += rtx_cost (XVECEXP (x, i, j));
  477.  
  478.   return total;
  479. }
  480.  
  481. /* Clear the hash table and initialize each register with its own quantity,
  482.    for a new basic block.  */
  483.  
  484. static void
  485. new_basic_block ()
  486. {
  487.   register int i;
  488.   register int vecsize = max_reg * sizeof (rtx);
  489.   next_qty = max_reg;
  490.  
  491.   bzero (reg_rtx, vecsize);
  492.   bzero (reg_tick, vecsize);
  493.  
  494.   bcopy (all_minus_one, reg_in_table, vecsize);
  495.   bcopy (all_minus_one, reg_next_eqv, vecsize);
  496.   bcopy (all_minus_one, reg_prev_eqv, vecsize);
  497.   bcopy (consec_ints, reg_qty, vecsize);
  498.  
  499.   for (i = 0; i < max_qty; i++)
  500.     {
  501.       qty_first_reg[i] = i;
  502.       qty_last_reg[i] = i;
  503.       qty_const[i] = 0;
  504.       qty_const_insn[i] = 0;
  505.     }
  506.  
  507.   for (i = 0; i < NBUCKETS; i++)
  508.     {
  509.       register struct table_elt *this, *next;
  510.       for (this = table[i]; this; this = next)
  511.     {
  512.       next = this->next_same_hash;
  513.       free_element (this);
  514.     }
  515.     }
  516.  
  517.   bzero (table, sizeof table);
  518.  
  519.   prev_insn_cc0 = 0;
  520.   prev_insn_explicit_cc0 = 0;
  521.   prev_insn = 0;
  522. }
  523.  
  524. /* Say that register REG contains a quantity not in any register before.  */
  525.  
  526. static void
  527. make_new_qty (reg)
  528.      register int reg;
  529. {
  530.   register int q;
  531.  
  532.   q = reg_qty[reg] = next_qty++;
  533.   qty_first_reg[q] = reg;
  534.   qty_last_reg[q] = reg;
  535. }
  536.  
  537. /* Make reg NEW equivalent to reg OLD.
  538.    OLD is not changing; NEW is.  */
  539.  
  540. static void
  541. make_regs_eqv (new, old)
  542.      register int new, old;
  543. {
  544.   register int lastr, firstr;
  545.   register int q = reg_qty[old];
  546.  
  547.   /* Nothing should become eqv until it has a "non-invalid" qty number.  */
  548.   if (q == old)
  549.     abort ();
  550.  
  551.   reg_qty[new] = q;
  552.   firstr = qty_first_reg[q];
  553.   lastr = qty_last_reg[q];
  554.  
  555.   /* Prefer pseudo regs to hard regs with the same value.
  556.      Among pseudos, if NEW will live longer than any other reg of the same qty,
  557.      and that is beyond the current basic block,
  558.      make it the new canonical replacement for this qty.  */
  559.   if (new >= FIRST_PSEUDO_REGISTER
  560.       && (firstr < FIRST_PSEUDO_REGISTER
  561.       || ((uid_cuid[regno_last_uid[new]] > cse_basic_block_end
  562.            || uid_cuid[regno_first_uid[new]] < cse_basic_block_start)
  563.           && (uid_cuid[regno_last_uid[new]]
  564.           > uid_cuid[regno_last_uid[firstr]]))))
  565.     {
  566.       reg_prev_eqv[firstr] = new;
  567.       reg_next_eqv[new] = firstr;
  568.       reg_prev_eqv[new] = -1;
  569.       qty_first_reg[q] = new;
  570.     }
  571.   else
  572.     {
  573.       /* If NEW is a hard reg, insert at end.
  574.      Otherwise, insert before any hard regs that are at the end.  */
  575.       while (lastr < FIRST_PSEUDO_REGISTER && new >= FIRST_PSEUDO_REGISTER)
  576.     lastr = reg_prev_eqv[lastr];
  577.       reg_next_eqv[new] = reg_next_eqv[lastr];
  578.       if (reg_next_eqv[lastr] >= 0)
  579.     reg_prev_eqv[reg_next_eqv[lastr]] = new;
  580.       else
  581.     qty_last_reg[q] = new;
  582.       reg_next_eqv[lastr] = new;
  583.       reg_prev_eqv[new] = lastr;
  584.     }
  585. }
  586.  
  587. /* Discard the records of what is in register REG.  */
  588.  
  589. static void
  590. reg_invalidate (reg)
  591.      register int reg;
  592. {
  593.   register int n = reg_next_eqv[reg];
  594.   register int p = reg_prev_eqv[reg];
  595.   register int q = reg_qty[reg];
  596.  
  597.   reg_tick[reg]++;
  598.  
  599.   if (q == reg)
  600.     {
  601.       /* Save time if already invalid */
  602.       /* It shouldn't be linked to anything if it's invalid.  */
  603.       if (reg_prev_eqv[q] != -1)
  604.     abort ();
  605.       if (reg_next_eqv[q] != -1)
  606.     abort ();
  607.       return;
  608.     }
  609.  
  610.   if (n != -1)
  611.     reg_prev_eqv[n] = p;
  612.   else
  613.     qty_last_reg[q] = p;
  614.   if (p != -1)
  615.     reg_next_eqv[p] = n;
  616.   else
  617.     qty_first_reg[q] = n;
  618.  
  619.   reg_qty[reg] = reg;
  620.   qty_first_reg[reg] = reg;
  621.   qty_last_reg[reg] = reg;
  622.   reg_next_eqv[reg] = -1;
  623.   reg_prev_eqv[reg] = -1;
  624. }
  625.  
  626. /* Remove any invalid expressions from the hash table
  627.    that refer to any of the registers contained in expression X.
  628.  
  629.    Make sure that newly inserted references to those registers
  630.    as subexpressions will be considered valid.
  631.  
  632.    mention_regs is not called when a register itself
  633.    is being stored in the table.  */
  634.  
  635. static void
  636. mention_regs (x)
  637.      rtx x;
  638. {
  639.   register enum rtx_code code;
  640.   register int i, j;
  641.   register char *fmt;
  642.  
  643.   if (x == 0)
  644.     return;
  645.  
  646.   code = GET_CODE (x);
  647.   if (code == REG)
  648.     {
  649.       register int regno = REGNO (x);
  650.       reg_rtx[regno] = x;
  651.  
  652.       if (reg_in_table[regno] >= 0 && reg_in_table[regno] != reg_tick[regno])
  653.     remove_invalid_refs (regno);
  654.  
  655.       reg_in_table[regno] = reg_tick[regno];
  656.  
  657.       return;
  658.     }
  659.  
  660.   fmt = GET_RTX_FORMAT (code);
  661.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  662.     if (fmt[i] == 'e')
  663.       mention_regs (XEXP (x, i));
  664.     else if (fmt[i] == 'E')
  665.       for (j = 0; j < XVECLEN (x, i); j++)
  666.     mention_regs (XVECEXP (x, i, j));
  667. }
  668.  
  669. /* Update the register quantities for inserting X into the hash table
  670.    with a value equivalent to CLASSP.
  671.    (If CLASSP is not a REG or a SUBREG, it is irrelevant.)
  672.    If MODIFIED is nonzero, X is a destination; it is being modified.
  673.    Note that reg_invalidate should be called on a register
  674.    before insert_regs is done on that register with MODIFIED != 0.
  675.  
  676.    Nonzero value means that elements of reg_qty have changed
  677.    so X's hash code may be different.  */
  678.  
  679. static int
  680. insert_regs (x, classp, modified)
  681.      rtx x;
  682.      struct table_elt *classp;
  683.      int modified;
  684. {
  685.   if (GET_CODE (x) == REG)
  686.     {
  687.       register int regno = REGNO (x);
  688.       reg_rtx[regno] = x;
  689.       if (modified || reg_qty[regno] == regno)
  690.     {
  691.       if (classp && GET_CODE (classp->exp) == REG)
  692.         {
  693.           make_regs_eqv (regno, REGNO (classp->exp));
  694.           /* Make sure reg_rtx is set up even for regs
  695.          not explicitly set (such as function value).  */
  696.           reg_rtx[REGNO (classp->exp)] = classp->exp;
  697.         }
  698.       else
  699.         make_new_qty (regno);
  700.       return 1;
  701.     }
  702.     }
  703.   /* Copying a subreg into a subreg makes the regs equivalent,
  704.      but only if the entire regs' mode is within one word.
  705.      Copying one reg of a DImode into one reg of another DImode
  706.      does not make them equivalent.  */
  707.   else if (GET_CODE (x) == SUBREG
  708.        && GET_CODE (SUBREG_REG (x)) == REG
  709.        && GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))) <= UNITS_PER_WORD
  710.        && (modified
  711.            || reg_qty[REGNO (SUBREG_REG (x))] == REGNO (SUBREG_REG (x))))
  712.     {
  713.       if (classp && GET_CODE (classp->exp) == SUBREG
  714.       && GET_CODE (SUBREG_REG (classp->exp)) == REG
  715.       && GET_MODE (SUBREG_REG (classp->exp)) == GET_MODE (SUBREG_REG (x)))
  716.     {
  717.       int oregno = REGNO (SUBREG_REG (classp->exp));
  718.       make_regs_eqv (REGNO (SUBREG_REG (x)), oregno);
  719.       /* Make sure reg_rtx is set up even for regs
  720.          not explicitly set (such as function value).  */
  721.       reg_rtx[oregno] = SUBREG_REG (classp->exp);
  722.     }
  723.       else
  724.     make_new_qty (REGNO (SUBREG_REG (x)));
  725.       return 1;
  726.     }
  727.   else
  728.     mention_regs (x);
  729.   return 0;
  730. }
  731.  
  732. /* Look in or update the hash table.  */
  733.  
  734. /* Put the element ELT on the list of free elements.  */
  735.  
  736. static void
  737. free_element (elt)
  738.      struct table_elt *elt;
  739. {
  740.   elt->next_same_hash = free_element_chain;
  741.   free_element_chain = elt;
  742. }
  743.  
  744. /* Return an element that is free for use.  */
  745.  
  746. static struct table_elt *
  747. get_element ()
  748. {
  749.   struct table_elt *elt = free_element_chain;
  750.   if (elt)
  751.     {
  752.       free_element_chain = elt->next_same_hash;
  753.       return elt;
  754.     }
  755.   n_elements_made++;
  756.   return (struct table_elt *) oballoc (sizeof (struct table_elt));
  757. }
  758.  
  759. /* Remove table element ELT from use in the table.
  760.    HASH is its hash code, made using the HASH macro.
  761.    It's an argument because often that is known in advance
  762.    and we save much time not recomputing it.  */
  763.  
  764. static void
  765. remove (elt, hash)
  766.      register struct table_elt *elt;
  767.      int hash;
  768. {
  769.   if (elt == 0)
  770.     return;
  771.  
  772.   /* Mark this element as removed.  See cse_insn.  */
  773.   elt->first_same_value = 0;
  774.  
  775.   /* Remove the table element from its equivalence class.  */
  776.      
  777.   {
  778.     register struct table_elt *prev = elt->prev_same_value;
  779.     register struct table_elt *next = elt->next_same_value;
  780.  
  781.     if (next) next->prev_same_value = prev;
  782.  
  783.     if (prev)
  784.       prev->next_same_value = next;
  785.     else
  786.       {
  787.     register struct table_elt *newfirst = next;
  788.     while (next)
  789.       {
  790.         next->first_same_value = newfirst;
  791.         next = next->next_same_value;
  792.       }
  793.       }
  794.   }
  795.  
  796.   /* Remove the table element from its hash bucket.  */
  797.  
  798.   {
  799.     register struct table_elt *prev = elt->prev_same_hash;
  800.     register struct table_elt *next = elt->next_same_hash;
  801.  
  802.     if (next) next->prev_same_hash = prev;
  803.  
  804.     if (prev)
  805.       prev->next_same_hash = next;
  806.     else
  807.       table[hash] = next; 
  808.   }
  809.  
  810.   /* Remove the table element from its related-value circular chain.  */
  811.  
  812.   if (elt->related_value != 0 && elt->related_value != elt)
  813.     {
  814.       register struct table_elt *p = elt->related_value;
  815.       while (p->related_value != elt)
  816.     p = p->related_value;
  817.       p->related_value = elt->related_value;
  818.       if (p->related_value == p)
  819.     p->related_value = 0;
  820.     }
  821.  
  822.   free_element (elt);
  823. }
  824.  
  825. /* Look up X in the hash table and return its table element,
  826.    or 0 if X is not in the table.
  827.  
  828.    MODE is the machine-mode of X, or if X is an integer constant
  829.    with VOIDmode then MODE is the mode with which X will be used.
  830.  
  831.    Here we are satisfied to find an expression whose tree structure
  832.    looks like X.  */
  833.  
  834. static struct table_elt *
  835. lookup (x, hash, mode)
  836.      rtx x;
  837.      int hash;
  838.      enum machine_mode mode;
  839. {
  840.   register struct table_elt *p;
  841.  
  842.   for (p = table[hash]; p; p = p->next_same_hash)
  843.     if (mode == p->mode && (x == p->exp || exp_equiv_p (x, p->exp, 1)))
  844.       return p;
  845.  
  846.   return 0;
  847. }
  848.  
  849. /* Like `lookup' but don't care whether the table element uses invalid regs.
  850.    Also ignore discrepancies in the machine mode of a register.  */
  851.  
  852. static struct table_elt *
  853. lookup_for_remove (x, hash, mode)
  854.      rtx x;
  855.      int hash;
  856.      enum machine_mode mode;
  857. {
  858.   register struct table_elt *p;
  859.  
  860.   if (GET_CODE (x) == REG)
  861.     {
  862.       int regno = REGNO (x);
  863.       /* Don't check the machine mode when comparing registers;
  864.      invalidating (REG:SI 0) also invalidates (REG:DF 0).  */
  865.       for (p = table[hash]; p; p = p->next_same_hash)
  866.     if (GET_CODE (p->exp) == REG
  867.         && REGNO (p->exp) == regno)
  868.       return p;
  869.     }
  870.   else
  871.     {
  872.       for (p = table[hash]; p; p = p->next_same_hash)
  873.     if (mode == p->mode && (x == p->exp || exp_equiv_p (x, p->exp, 0)))
  874.       return p;
  875.     }
  876.  
  877.   return 0;
  878. }
  879.  
  880. /* Look for an expression equivalent to X and with code CODE.
  881.    If one is found, return that expression.  */
  882.  
  883. static rtx
  884. lookup_as_function (x, code)
  885.      rtx x;
  886.      enum rtx_code code;
  887. {
  888.   register struct table_elt *p = lookup (x, safe_hash (x, 0) % NBUCKETS,
  889.                      GET_MODE (x));
  890.   if (p == 0)
  891.     return 0;
  892.  
  893.   for (p = p->first_same_value; p; p = p->next_same_value)
  894.     {
  895.       if (GET_CODE (p->exp) == code
  896.       /* Make sure this is a valid entry in the table.  */
  897.       && (exp_equiv_p (XEXP (p->exp, 0), XEXP (p->exp, 0), 1)))
  898.     return p->exp;
  899.     }
  900.   
  901.   return 0;
  902. }
  903.  
  904. /* Insert X in the hash table, assuming HASH is its hash code
  905.    and CLASSP is the current first element of the class it should go in
  906.    (or 0 if a new class should be made).
  907.    It is inserted at the proper position to keep the class in
  908.    the order cheapest first.
  909.  
  910.    MODE is the machine-mode of X, or if X is an integer constant
  911.    with VOIDmode then MODE is the mode with which X will be used.
  912.  
  913.    For elements of equal cheapness, the most recent one
  914.    goes in front, except that the first element in the list
  915.    remains first unless a cheaper element is added.
  916.  
  917.    The in_memory field in the hash table element is set to 0.
  918.    The caller must set it nonzero if appropriate.
  919.  
  920.    You should call insert_regs (X, CLASSP, MODIFY) before calling here,
  921.    and if insert_regs returns a nonzero value
  922.    you must then recompute its hash code before calling here.
  923.  
  924.    If necessary, update table showing constant values of quantities.  */
  925.  
  926. #define CHEAPER(X,Y)    \
  927.    (((X)->cost < (Y)->cost) ||                        \
  928.     ((X)->cost == (Y)->cost                        \
  929.      && GET_CODE ((X)->exp) == REG && GET_CODE ((Y)->exp) == REG    \
  930.      && (uid_cuid[regno_last_uid[REGNO ((X)->exp)]] > cse_basic_block_end        \
  931.      || uid_cuid[regno_first_uid[REGNO ((X)->exp)]] < cse_basic_block_start)    \
  932.      && (uid_cuid[regno_last_uid[REGNO ((X)->exp)]]            \
  933.      > uid_cuid[regno_last_uid[REGNO ((Y)->exp)]])))
  934.  
  935. static struct table_elt *
  936. insert (x, classp, hash, mode)
  937.      register rtx x;
  938.      register struct table_elt *classp;
  939.      int hash;
  940.      enum machine_mode mode;
  941. {
  942.   register struct table_elt *elt;
  943.  
  944.   /* Put an element for X into the right hash bucket.  */
  945.  
  946.   elt = get_element ();
  947.   elt->exp = x;
  948.   elt->cost = rtx_cost (x) * 2;
  949.   /* Make pseudo regs a little cheaper than hard regs.  */
  950.   if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER)
  951.     elt->cost -= 1;
  952.   elt->next_same_value = 0;
  953.   elt->prev_same_value = 0;
  954.   elt->next_same_hash = table[hash];
  955.   elt->prev_same_hash = 0;
  956.   elt->related_value = 0;
  957.   elt->in_memory = 0;
  958.   elt->equivalence_only = 0;
  959.   elt->mode = mode;
  960.   if (table[hash])
  961.     table[hash]->prev_same_hash = elt;
  962.   table[hash] = elt;
  963.  
  964.   /* Put it into the proper value-class.  */
  965.   if (classp)
  966.     {
  967.       if (CHEAPER (elt, classp))
  968.     /** Insert at the head of the class */
  969.     {
  970.       register struct table_elt *p;
  971.       elt->next_same_value = classp;
  972.       classp->prev_same_value = elt;
  973.       elt->first_same_value = elt;
  974.  
  975.       for (p = classp; p; p = p->next_same_value)
  976.         p->first_same_value = elt;
  977.     }
  978.       else
  979.     {
  980.       /* Insert not at head of the class.  */
  981.       /* Put it after the last element cheaper than X.  */
  982.       register struct table_elt *p, *next;
  983.       for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
  984.            p = next);
  985.       /* Put it after P and before NEXT.  */
  986.       elt->next_same_value = next;
  987.       if (next)
  988.         next->prev_same_value = elt;
  989.       elt->prev_same_value = p;
  990.       p->next_same_value = elt;
  991.       elt->first_same_value = classp;
  992.     }
  993.     }
  994.   else
  995.     elt->first_same_value = elt;
  996.  
  997.   if ((CONSTANT_P (x) || GET_CODE (x) == CONST_DOUBLE || FIXED_BASE_PLUS_P (x))
  998.       && GET_CODE (elt->first_same_value->exp) == REG)
  999.     {
  1000.       qty_const[reg_qty[REGNO (elt->first_same_value->exp)]] = x;
  1001.       qty_const_insn[reg_qty[REGNO (elt->first_same_value->exp)]] = this_insn;
  1002.     }
  1003.  
  1004.   if (GET_CODE (x) == REG)
  1005.     {
  1006.       if (elt->next_same_value != 0
  1007.       && (CONSTANT_P (elt->next_same_value->exp)
  1008.           || GET_CODE (elt->next_same_value->exp) == CONST_DOUBLE
  1009.           || FIXED_BASE_PLUS_P (elt->next_same_value->exp)))
  1010.     {
  1011.       qty_const[reg_qty[REGNO (x)]] = elt->next_same_value->exp;
  1012.       qty_const_insn[reg_qty[REGNO (x)]] = this_insn;
  1013.     }
  1014.       if (CONSTANT_P (elt->first_same_value->exp)
  1015.       || GET_CODE (elt->first_same_value->exp) == CONST_DOUBLE
  1016.       || FIXED_BASE_PLUS_P (elt->first_same_value->exp))
  1017.     {
  1018.       qty_const[reg_qty[REGNO (x)]] = elt->first_same_value->exp;
  1019.       qty_const_insn[reg_qty[REGNO (x)]] = this_insn;
  1020.     }
  1021.     }
  1022.  
  1023.   /* If this is a constant with symbolic value,
  1024.      and it has a term with an explicit integer value,
  1025.      link it up with related expressions.  */
  1026.   if (GET_CODE (x) == CONST)
  1027.     {
  1028.       rtx subexp = get_related_value (x);
  1029.       int subhash;
  1030.       struct table_elt *subelt, *subelt_prev;
  1031.  
  1032.       if (subexp != 0)
  1033.     {
  1034.       /* Get the integer-free subexpression in the hash table.  */
  1035.       subhash = safe_hash (subexp, mode) % NBUCKETS;
  1036.       subelt = lookup (subexp, subhash, mode);
  1037.       if (subelt == 0)
  1038.         subelt = insert (subexp, 0, subhash, mode);
  1039.       /* Initialize SUBELT's circular chain if it has none.  */
  1040.       if (subelt->related_value == 0)
  1041.         subelt->related_value = subelt;
  1042.       /* Find the element in the circular chain that precedes SUBELT.  */
  1043.       subelt_prev = subelt;
  1044.       while (subelt_prev->related_value != subelt)
  1045.         subelt_prev = subelt_prev->related_value;
  1046.       /* Put new ELT into SUBELT's circular chain just before SUBELT.
  1047.          This way the element that follows SUBELT is the oldest one.  */
  1048.       elt->related_value = subelt_prev->related_value;
  1049.       subelt_prev->related_value = elt;
  1050.     }
  1051.     }
  1052.  
  1053.   return elt;
  1054. }
  1055.  
  1056. /* Remove from the hash table, or mark as invalid,
  1057.    all expressions whose values could be altered by storing in X.
  1058.    X is a register, a subreg, or a memory reference with nonvarying address
  1059.    (because, when a memory reference with a varying address is stored in,
  1060.    all memory references are removed by invalidate_memory
  1061.    so specific invalidation is superfluous).
  1062.  
  1063.    A nonvarying address may be just a register or just
  1064.    a symbol reference, or it may be either of those plus
  1065.    a numeric offset.  */
  1066.  
  1067. static void
  1068. invalidate (x)
  1069.      rtx x;
  1070. {
  1071.   register int i;
  1072.   register struct table_elt *p;
  1073.   register rtx base;
  1074.   register int start, end;
  1075.  
  1076.   /* If X is a register, dependencies on its contents
  1077.      are recorded through the qty number mechanism.
  1078.      Just change the qty number of the register,
  1079.      mark it as invalid for expressions that refer to it,
  1080.      and remove it itself.  */
  1081.  
  1082.   if (GET_CODE (x) == REG)
  1083.     {
  1084.       register int hash = HASH (x, 0);
  1085.       reg_invalidate (REGNO (x));
  1086.       remove (lookup_for_remove (x, hash, GET_MODE (x)), hash);
  1087.       return;
  1088.     }
  1089.  
  1090.   if (GET_CODE (x) == SUBREG)
  1091.     {
  1092.       if (GET_CODE (SUBREG_REG (x)) != REG)
  1093.     abort ();
  1094.       invalidate (SUBREG_REG (x));
  1095.       return;
  1096.     }
  1097.  
  1098.   /* X is not a register; it must be a memory reference with
  1099.      a nonvarying address.  Remove all hash table elements
  1100.      that refer to overlapping pieces of memory.  */
  1101.  
  1102.   if (GET_CODE (x) != MEM)
  1103.     abort ();
  1104.   base = XEXP (x, 0);
  1105.   start = 0;
  1106.  
  1107.   /* Registers with nonvarying addresses usually have constant equivalents;
  1108.      but the frame pointer register is also possible.  */
  1109.   if (GET_CODE (base) == REG
  1110.       && qty_const[reg_qty[REGNO (base)]] != 0)
  1111.     base = qty_const[reg_qty[REGNO (base)]];
  1112.  
  1113.   if (GET_CODE (base) == CONST)
  1114.     base = XEXP (base, 0);
  1115.   if (GET_CODE (base) == PLUS
  1116.       && GET_CODE (XEXP (base, 1)) == CONST_INT)
  1117.     {
  1118.       start = INTVAL (XEXP (base, 1));
  1119.       base = XEXP (base, 0);
  1120.     }
  1121.  
  1122.   end = start + GET_MODE_SIZE (GET_MODE (x));
  1123.   for (i = 0; i < NBUCKETS; i++)
  1124.     {
  1125.       register struct table_elt *next;
  1126.       for (p = table[i]; p; p = next)
  1127.     {
  1128.       next = p->next_same_hash;
  1129.       if (refers_to_mem_p (p->exp, base, start, end))
  1130.         remove (p, i);
  1131.     }
  1132.     }
  1133. }
  1134.  
  1135. /* Remove all expressions that refer to register REGNO,
  1136.    since they are already invalid, and we are about to
  1137.    mark that register valid again and don't want the old
  1138.    expressions to reappear as valid.  */
  1139.  
  1140. static void
  1141. remove_invalid_refs (regno)
  1142.      int regno;
  1143. {
  1144.   register int i;
  1145.   register struct table_elt *p, *next;
  1146.   register rtx x = reg_rtx[regno];
  1147.  
  1148.   for (i = 0; i < NBUCKETS; i++)
  1149.     for (p = table[i]; p; p = next)
  1150.       {
  1151.     next = p->next_same_hash;
  1152.     if (GET_CODE (p->exp) != REG && refers_to_p (p->exp, x))
  1153.       remove (p, i);
  1154.       }
  1155. }
  1156.  
  1157. /* Remove from the hash table all expressions that reference memory,
  1158.    or some of them as specified by *WRITES.  */
  1159.  
  1160. static void
  1161. invalidate_memory (writes)
  1162.      struct write_data *writes;
  1163. {
  1164.   register int i;
  1165.   register struct table_elt *p, *next;
  1166.   int all = writes->all;
  1167.   int nonscalar = writes->nonscalar;
  1168.  
  1169.   for (i = 0; i < NBUCKETS; i++)
  1170.     for (p = table[i]; p; p = next)
  1171.       {
  1172.     next = p->next_same_hash;
  1173.     if (p->in_memory
  1174.         && (all
  1175.         || (nonscalar && p->in_struct)
  1176.         || cse_rtx_addr_varies_p (p->exp)))
  1177.       remove (p, i);
  1178.       }
  1179. }
  1180.  
  1181. /* Return the value of the integer term in X, if one is apparent;
  1182.    otherwise return 0.
  1183.    We do not check extremely carefully for the presence of integer terms
  1184.    but rather consider only the cases that `insert' notices
  1185.    for the `related_value' field.  */
  1186.  
  1187. static int
  1188. get_integer_term (x)
  1189.      rtx x;
  1190. {
  1191.   if (GET_CODE (x) == CONST)
  1192.     x = XEXP (x, 0);
  1193.  
  1194.   if (GET_CODE (x) == MINUS
  1195.       && GET_CODE (XEXP (x, 1)) == CONST_INT)
  1196.     return - INTVAL (XEXP (x, 1));
  1197.   if (GET_CODE (x) != PLUS)
  1198.     return 0;
  1199.   if (GET_CODE (XEXP (x, 0)) == CONST_INT)
  1200.     return INTVAL (XEXP (x, 0));
  1201.   if (GET_CODE (XEXP (x, 1)) == CONST_INT)
  1202.     return INTVAL (XEXP (x, 1));
  1203.   return 0;
  1204. }
  1205.  
  1206. static rtx
  1207. get_related_value (x)
  1208.      rtx x;
  1209. {
  1210.   if (GET_CODE (x) != CONST)
  1211.     return 0;
  1212.   x = XEXP (x, 0);
  1213.   if (GET_CODE (x) == PLUS)
  1214.     {
  1215.       if (GET_CODE (XEXP (x, 0)) == CONST_INT)
  1216.     return XEXP (x, 1);
  1217.       if (GET_CODE (XEXP (x, 1)) == CONST_INT)
  1218.     return XEXP (x, 0);
  1219.     }
  1220.   else if (GET_CODE (x) == MINUS
  1221.        && GET_CODE (XEXP (x, 1)) == CONST_INT)
  1222.     return XEXP (x, 0);
  1223.   return 0;
  1224. }
  1225.  
  1226. /* Given an expression X of type CONST,
  1227.    and ELT which is its table entry (or 0 if it
  1228.    is not in the hash table),
  1229.    return an alternate expression for X as a register plus integer.
  1230.    If none can be found or it would not be a valid address, return 0.  */
  1231.  
  1232. static rtx
  1233. use_related_value (x, elt)
  1234.      rtx x;
  1235.      struct table_elt *elt;
  1236. {
  1237.   register struct table_elt *relt = 0;
  1238.   register struct table_elt *p;
  1239.   int offset;
  1240.   rtx addr;
  1241.  
  1242.   /* First, is there anything related known?
  1243.      If we have a table element, we can tell from that.
  1244.      Otherwise, must look it up.  */
  1245.  
  1246.   if (elt != 0 && elt->related_value != 0)
  1247.     relt = elt;
  1248.   else if (elt == 0 && GET_CODE (x) == CONST)
  1249.     {
  1250.       rtx subexp = get_related_value (x);
  1251.       if (subexp != 0)
  1252.     relt = lookup (subexp,
  1253.                safe_hash (subexp, GET_MODE (subexp)) % NBUCKETS,
  1254.                GET_MODE (subexp));
  1255.     }
  1256.  
  1257.   if (relt == 0)
  1258.     return 0;
  1259.  
  1260.   /* Search all related table entries for one that has an
  1261.      equivalent register.  */
  1262.  
  1263.   p = relt;
  1264.   while (1)
  1265.     {
  1266.       if (p->first_same_value != 0
  1267.       && GET_CODE (p->first_same_value->exp) == REG)
  1268.     break;
  1269.       p = p->related_value;
  1270.  
  1271.       /* We went all the way around, so there is nothing to be found.
  1272.      Return failure.  */
  1273.       if (p == relt)
  1274.     return 0;
  1275.       /* Perhaps RELT was in the table for some other reason and
  1276.      it has no related values recorded.  */
  1277.       if (p == 0)
  1278.     return 0;
  1279.     }
  1280.  
  1281.   /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity.  */
  1282.   offset = (get_integer_term (x) - get_integer_term (p->exp));
  1283.   addr = plus_constant (p->first_same_value->exp, offset);
  1284.   if (memory_address_p (QImode, addr))
  1285.     return addr;
  1286.   return 0;
  1287. }
  1288.  
  1289. /* Hash an rtx.  We are careful to make sure the value is never negative.
  1290.    Equivalent registers hash identically.
  1291.    MODE is used in hashing for CONST_INTs only;
  1292.    otherwise the mode of X is used.
  1293.  
  1294.    Store 1 in do_not_record if any subexpression is volatile.
  1295.  
  1296.    Store 1 in hash_arg_in_memory if X contains a MEM rtx
  1297.    which does not have the RTX_UNCHANGING_P bit set.
  1298.    In this case, also store 1 in hash_arg_in_struct
  1299.    if there is a MEM rtx which has the MEM_IN_STRUCT_P bit set.
  1300.  
  1301.    Note that cse_insn knows that the hash code of a MEM expression
  1302.    is just (int) MEM plus the hash code of the address.
  1303.    It also knows it can use HASHREG to get the hash code of (REG n).  */
  1304.  
  1305. #define HASHBITS 16
  1306.  
  1307. #define HASHREG(RTX) \
  1308.  ((((int) REG << 7) + reg_qty[REGNO (RTX)]) % NBUCKETS)
  1309.  
  1310. static int
  1311. canon_hash (x, mode)
  1312.      rtx x;
  1313.      enum machine_mode mode;
  1314. {
  1315.   register int i, j;
  1316.   register int hash = 0;
  1317.   register enum rtx_code code;
  1318.   register char *fmt;
  1319.  
  1320.   /* repeat is used to turn tail-recursion into iteration.  */
  1321.  repeat:
  1322.   if (x == 0)
  1323.     return hash;
  1324.  
  1325.   code = GET_CODE (x);
  1326.   switch (code)
  1327.     {
  1328.     case REG:
  1329.       {
  1330.     /* We do not invalidate anything on pushing or popping
  1331.        because they cannot change anything but the stack pointer;
  1332.        but that means we must consider the stack pointer volatile
  1333.        since it can be changed "mysteriously".  */
  1334.  
  1335.     register int regno = REGNO (x);
  1336.     if (regno == STACK_POINTER_REGNUM
  1337.         || (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]))
  1338.       {
  1339.         do_not_record = 1;
  1340.         return 0;
  1341.       }
  1342.     return hash + ((int) REG << 7) + reg_qty[regno];
  1343.       }
  1344.  
  1345.     case CONST_INT:
  1346.       hash += ((int) mode + ((int) CONST_INT << 7)
  1347.            + INTVAL (x) + (INTVAL (x) >> HASHBITS));
  1348.       return ((1 << HASHBITS) - 1) & hash;
  1349.  
  1350.     case CONST_DOUBLE:
  1351.       /* This is like the general case, except that it only counts
  1352.      the first two elements.  */
  1353.       hash += (int) code + (int) GET_MODE (x);
  1354.       {
  1355.     int i;
  1356.     for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
  1357.       {
  1358.         int tem = XINT (x, i);
  1359.         hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS));
  1360.       }
  1361.       }
  1362.       return hash;
  1363.  
  1364.       /* Assume there is only one rtx object for any given label.  */
  1365.     case LABEL_REF:
  1366.       /* Use `and' to ensure a positive number.  */
  1367.       return (hash + ((int) LABEL_REF << 7)
  1368.           + ((int) XEXP (x, 0) & ((1 << HASHBITS) - 1)));
  1369.  
  1370.     case SYMBOL_REF:
  1371.       return (hash + ((int) SYMBOL_REF << 7)
  1372.           + ((int) XEXP (x, 0) & ((1 << HASHBITS) - 1)));
  1373.  
  1374.     case MEM:
  1375.       if (MEM_VOLATILE_P (x))
  1376.     {
  1377.       do_not_record = 1;
  1378.       return 0;
  1379.     }
  1380.       if (! RTX_UNCHANGING_P (x))
  1381.     {
  1382.       hash_arg_in_memory = 1;
  1383.       if (MEM_IN_STRUCT_P (x)) hash_arg_in_struct = 1;
  1384.     }
  1385.       /* Now that we have already found this special case,
  1386.      might as well speed it up as much as possible.  */
  1387.       hash += (int) MEM;
  1388.       x = XEXP (x, 0);
  1389.       goto repeat;
  1390.  
  1391.     case PRE_DEC:
  1392.     case PRE_INC:
  1393.     case POST_DEC:
  1394.     case POST_INC:
  1395.     case PC:
  1396.     case CC0:
  1397.     case CALL:
  1398.       do_not_record = 1;
  1399.       return 0;
  1400.  
  1401.     case ASM_OPERANDS:
  1402.       if (MEM_VOLATILE_P (x))
  1403.     {
  1404.       do_not_record = 1;
  1405.       return 0;
  1406.     }
  1407.     }
  1408.  
  1409.   i = GET_RTX_LENGTH (code) - 1;
  1410.   hash += (int) code + (int) GET_MODE (x);
  1411.   fmt = GET_RTX_FORMAT (code);
  1412.   for (; i >= 0; i--)
  1413.     {
  1414.       if (fmt[i] == 'e')
  1415.     {
  1416.       /* If we are about to do the last recursive call
  1417.          needed at this level, change it into iteration.
  1418.          This function  is called enough to be worth it.  */
  1419.       if (i == 0)
  1420.         {
  1421.           x = XEXP (x, 0);
  1422.           goto repeat;
  1423.         }
  1424.       hash += canon_hash (XEXP (x, i), 0);
  1425.     }
  1426.       else if (fmt[i] == 'E')
  1427.     for (j = 0; j < XVECLEN (x, i); j++)
  1428.       hash += canon_hash (XVECEXP (x, i, j), 0);
  1429.       else if (fmt[i] == 's')
  1430.     {
  1431.       register char *p = XSTR (x, i);
  1432.       if (p)
  1433.         while (*p)
  1434.           {
  1435.         register int tem = *p++;
  1436.         hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS));
  1437.           }
  1438.     }
  1439.       else
  1440.     {
  1441.       register int tem = XINT (x, i);
  1442.       hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS));
  1443.     }
  1444.     }
  1445.   return hash;
  1446. }
  1447.  
  1448. /* Like canon_hash but with no side effects.  */
  1449.  
  1450. static int
  1451. safe_hash (x, mode)
  1452.      rtx x;
  1453.      enum machine_mode mode;
  1454. {
  1455.   int save_do_not_record = do_not_record;
  1456.   int save_hash_arg_in_memory = hash_arg_in_memory;
  1457.   int save_hash_arg_in_struct = hash_arg_in_struct;
  1458.   int hash = canon_hash (x, mode);
  1459.   hash_arg_in_memory = save_hash_arg_in_memory;
  1460.   hash_arg_in_struct = save_hash_arg_in_struct;
  1461.   do_not_record = save_do_not_record;
  1462.   return hash;
  1463. }
  1464.  
  1465. /* Return 1 iff X and Y would canonicalize into the same thing,
  1466.    without actually constructing the canonicalization of either one.
  1467.    If VALIDATE is nonzero,
  1468.    we assume X is an expression being processed from the rtl
  1469.    and Y was found in the hash table.  We check register refs
  1470.    in Y for being marked as valid.  */
  1471.  
  1472. static int
  1473. exp_equiv_p (x, y, validate)
  1474.      rtx x, y;
  1475.      int validate;
  1476. {
  1477.   register int i;
  1478.   register enum rtx_code code;
  1479.   register char *fmt;
  1480.  
  1481.   /* Note: it is incorrect to assume an expression is equivalent to itself
  1482.      if VALIDATE is nonzero.  */
  1483.   if (x == y && !validate)
  1484.     return 1;
  1485.   if (x == 0 || y == 0)
  1486.     return x == y;
  1487.   code = GET_CODE (x);
  1488.   if (code != GET_CODE (y))
  1489.     return 0;
  1490.  
  1491.   switch (code)
  1492.     {
  1493.     case PC:
  1494.     case CC0:
  1495.       return x == y;
  1496.  
  1497.     case CONST_INT:
  1498.       return XINT (x, 0) == XINT (y, 0);
  1499.  
  1500.     case LABEL_REF:
  1501.     case SYMBOL_REF:
  1502.       return XEXP (x, 0) == XEXP (y, 0);
  1503.  
  1504.     case REG:
  1505.       return (reg_qty[REGNO (x)] == reg_qty[REGNO (y)]
  1506.           && (!validate
  1507.           || reg_in_table[REGNO (y)] == reg_tick[REGNO (y)]));
  1508.     }
  1509.  
  1510.   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
  1511.  
  1512.   if (GET_MODE (x) != GET_MODE (y))
  1513.     return 0;
  1514.  
  1515.   /* Compare the elements.  If any pair of corresponding elements
  1516.      fail to match, return 0 for the whole things.  */
  1517.  
  1518.   fmt = GET_RTX_FORMAT (code);
  1519.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1520.     {
  1521.       if (fmt[i] == 'e')
  1522.     {
  1523.       if (! exp_equiv_p (XEXP (x, i), XEXP (y, i), validate))
  1524.         return 0;
  1525.     }
  1526.       else if (fmt[i] == 'E')
  1527.     {
  1528.       int j;
  1529.       if (XVECLEN (x, i) != XVECLEN (y, i))
  1530.         return 0;
  1531.       for (j = 0; j < XVECLEN (x, i); j++)
  1532.         if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j), validate))
  1533.           return 0;
  1534.     }
  1535.       else if (fmt[i] == 's')
  1536.     {
  1537.       if (strcmp (XSTR (x, i), XSTR (y, i)))
  1538.         return 0;
  1539.     }
  1540.       else
  1541.     {
  1542.       if (XINT (x, i) != XINT (y, i))
  1543.         return 0;
  1544.     }
  1545.     }
  1546.   return 1;
  1547. }
  1548.  
  1549. /* Return 1 iff any subexpression of X matches Y.
  1550.    Here we do not require that X or Y be valid (for registers referred to)
  1551.    for being in the hash table.  */
  1552.  
  1553. int
  1554. refers_to_p (x, y)
  1555.      rtx x, y;
  1556. {
  1557.   register int i;
  1558.   register enum rtx_code code;
  1559.   register char *fmt;
  1560.  
  1561.  repeat:
  1562.   if (x == y)
  1563.     return 1;
  1564.   if (x == 0 || y == 0)
  1565.     return 0;
  1566.  
  1567.   code = GET_CODE (x);
  1568.   /* If X as a whole has the same code as Y, they may match.
  1569.      If so, return 1.  */
  1570.   if (code == GET_CODE (y))
  1571.     {
  1572.       if (exp_equiv_p (x, y, 0))
  1573.     return 1;
  1574.     }
  1575.  
  1576.   /* X does not match, so try its subexpressions.  */
  1577.  
  1578.   fmt = GET_RTX_FORMAT (code);
  1579.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1580.     if (fmt[i] == 'e')
  1581.       {
  1582.     if (i == 0)
  1583.       {
  1584.         x = XEXP (x, 0);
  1585.         goto repeat;
  1586.       }
  1587.     else
  1588.       if (refers_to_p (XEXP (x, i), y))
  1589.         return 1;
  1590.       }
  1591.     else if (fmt[i] == 'E')
  1592.       {
  1593.     int j;
  1594.     for (j = 0; j < XVECLEN (x, i); j++)
  1595.       if (refers_to_p (XVECEXP (x, i, j), y))
  1596.         return 1;
  1597.       }
  1598.  
  1599.   return 0;
  1600. }
  1601.  
  1602. /* Return 1 iff any subexpression of X refers to memory
  1603.    at an address of REG plus some offset
  1604.    such that any of the bytes' offsets fall between START (inclusive)
  1605.    and END (exclusive).
  1606.  
  1607.    The value is undefined if X is a varying address.
  1608.    This function is not used in such cases.
  1609.  
  1610.    When used in the cse pass, `qty_const' is nonzero, and it is used
  1611.    to treat an address that is a register with a known constant value
  1612.    as if it were that constant value.
  1613.    In the loop pass, `qty_const' is zero, so this is not done.  */
  1614.  
  1615. int
  1616. refers_to_mem_p (x, reg, start, end)
  1617.      rtx x, reg;
  1618.      int start, end;
  1619. {
  1620.   register int i;
  1621.   register enum rtx_code code;
  1622.   register char *fmt;
  1623.  
  1624.  repeat:
  1625.   if (x == 0)
  1626.     return 0;
  1627.  
  1628.   code = GET_CODE (x);
  1629.   if (code == MEM)
  1630.     {
  1631.       register rtx addr = XEXP (x, 0);    /* Get the address.  */
  1632.       int myend;
  1633.       if (GET_CODE (addr) == REG
  1634.       /* qty_const is 0 when outside the cse pass;
  1635.          at such times, this info is not available.  */
  1636.       && qty_const != 0
  1637.       && qty_const[reg_qty[REGNO (addr)]] != 0)
  1638.     addr = qty_const[reg_qty[REGNO (addr)]];
  1639.       if (GET_CODE (addr) == CONST)
  1640.     addr = XEXP (addr, 0);
  1641.  
  1642.       /* If ADDR is BASE, or BASE plus an integer, put
  1643.      the integer in I.  */
  1644.       if (addr == reg)
  1645.     i = 0;
  1646.       else if (GET_CODE (addr) == PLUS
  1647.            && XEXP (addr, 0) == reg
  1648.            && GET_CODE (XEXP (addr, 1)) == CONST_INT)
  1649.     i = INTVAL (XEXP (addr, 1));
  1650.       else
  1651.     return 0;
  1652.  
  1653.       myend = i + GET_MODE_SIZE (GET_MODE (x));
  1654.       return myend > start && i < end;
  1655.     }
  1656.  
  1657.   /* X does not match, so try its subexpressions.  */
  1658.  
  1659.   fmt = GET_RTX_FORMAT (code);
  1660.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1661.     if (fmt[i] == 'e')
  1662.       {
  1663.     if (i == 0)
  1664.       {
  1665.         x = XEXP (x, 0);
  1666.         goto repeat;
  1667.       }
  1668.     else
  1669.       if (refers_to_mem_p (XEXP (x, i), reg, start, end))
  1670.         return 1;
  1671.       }
  1672.     else if (fmt[i] == 'E')
  1673.       {
  1674.     int j;
  1675.     for (j = 0; j < XVECLEN (x, i); j++)
  1676.       if (refers_to_mem_p (XVECEXP (x, i, j), reg, start, end))
  1677.         return 1;
  1678.       }
  1679.  
  1680.   return 0;
  1681. }
  1682.  
  1683. /* Nonzero if X refers to memory at a varying address;
  1684.    except that a register which has at the moment a known constant value
  1685.    isn't considered variable.  */
  1686.  
  1687. static int
  1688. cse_rtx_addr_varies_p (x)
  1689.      rtx x;
  1690. {
  1691.   if (GET_CODE (x) == MEM
  1692.       && GET_CODE (XEXP (x, 0)) == REG
  1693.       && qty_const[reg_qty[REGNO (XEXP (x, 0))]] != 0)
  1694.     return 0;
  1695.   return rtx_addr_varies_p (x);
  1696. }
  1697.  
  1698. /* Canonicalize an expression:
  1699.    replace each register reference inside it
  1700.    with the "oldest" equivalent register.  */
  1701.  
  1702. static rtx
  1703. canon_reg (x)
  1704.      rtx x;
  1705. {
  1706.   register int i;
  1707.   register enum rtx_code code;
  1708.   register char *fmt;
  1709.  
  1710.   if (x == 0)
  1711.     return x;
  1712.  
  1713.   code = GET_CODE (x);
  1714.   switch (code)
  1715.     {
  1716.     case PC:
  1717.     case CC0:
  1718.     case CONST:
  1719.     case CONST_INT:
  1720.     case CONST_DOUBLE:
  1721.     case SYMBOL_REF:
  1722.     case LABEL_REF:
  1723.     case ADDR_VEC:
  1724.     case ADDR_DIFF_VEC:
  1725.       return x;
  1726.  
  1727.     case REG:
  1728.       {
  1729.     register rtx new;
  1730.     /* Never replace a hard reg, because hard regs can appear
  1731.        in more than one machine mode, and we must preserve the mode
  1732.        of each occurrence.  Also, some hard regs appear in
  1733.        MEMs that are shared and mustn't be altered.  */
  1734.     if (REGNO (x) < FIRST_PSEUDO_REGISTER)
  1735.       return x;
  1736.     new = reg_rtx[qty_first_reg[reg_qty[REGNO (x)]]];
  1737. #if defined( DSP56000 ) || defined( DSP96000 )
  1738.     return ( new && ( new->mode == x->mode )) ? new : x;
  1739. #else
  1740.     return new ? new : x;
  1741. #endif
  1742.       }
  1743.     }
  1744.  
  1745.   fmt = GET_RTX_FORMAT (code);
  1746.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1747.     {
  1748.       register int j;
  1749.  
  1750.       if (fmt[i] == 'e')
  1751.     XEXP (x, i) = canon_reg (XEXP (x, i));
  1752.       else if (fmt[i] == 'E')
  1753.     for (j = 0; j < XVECLEN (x, i); j++)
  1754.       XVECEXP (x, i, j) = canon_reg (XVECEXP (x, i, j));
  1755.     }
  1756.  
  1757.   return x;
  1758. }
  1759.  
  1760. /* If X is a nontrivial arithmetic operation on an argument
  1761.    for which a constant value can be determined, return
  1762.    the result of operating on that value, as a constant.
  1763.    Otherwise, return X, possibly with one or more operands
  1764.    modified by recursive calls to this function.
  1765.  
  1766.    If X is a register whose contents are known, we do NOT
  1767.    return those contents.  This is because an instruction that
  1768.    uses a register is usually faster than one that uses a constant.
  1769.  
  1770.    COPYFLAG is nonzero for memory addresses and subexpressions thereof.
  1771.    If COPYFLAG is nonzero, we avoid altering X itself
  1772.    by creating new structure when necessary.  In this case we
  1773.    can risk creating invalid structure because it will be tested.
  1774.    If COPYFLAG is zero, be careful not to substitute constants
  1775.    into expressions that cannot be simplified.  */
  1776.  
  1777. static rtx
  1778. fold_rtx (x, copyflag)
  1779.      rtx x;
  1780.      int copyflag;
  1781. {
  1782.   register enum rtx_code code;
  1783.   register char *fmt;
  1784.   register int i, val;
  1785.   rtx new = 0;
  1786.   int copied = ! copyflag;
  1787.   int width;
  1788.  
  1789.   /* Constant equivalents of first three operands of X;
  1790.      0 when no such equivalent is known.  */
  1791.   rtx const_arg0;
  1792.   rtx const_arg1;
  1793.   rtx const_arg2;
  1794.  
  1795.   if (x == 0)
  1796.     return x;
  1797.  
  1798.   width = GET_MODE_BITSIZE (GET_MODE (x));
  1799.  
  1800.   code = GET_CODE (x);
  1801.   switch (code)
  1802.     {
  1803.     case CONST:
  1804.     case CONST_INT:
  1805.     case CONST_DOUBLE:
  1806.     case SYMBOL_REF:
  1807.     case LABEL_REF:
  1808.     case PC:
  1809.     case CC0:
  1810.     case REG:
  1811.       /* No use simplifying an EXPR_LIST
  1812.      since they are used only for lists of args
  1813.      in a function call's REG_EQUAL note.  */
  1814.     case EXPR_LIST:
  1815.       return x;
  1816.  
  1817.   /* We must be careful when folding a memory address
  1818.      to avoid making it invalid.  So fold nondestructively
  1819.      and use the result only if it's valid.  */
  1820.     case MEM:
  1821.       {
  1822.     rtx newaddr = fold_rtx (XEXP (x, 0), 1);
  1823.     /* Save time if no change was made.  */
  1824.     if (XEXP (x, 0) == newaddr)
  1825.       return x;
  1826.  
  1827.     if (! memory_address_p (GET_MODE (x), newaddr)
  1828.         && memory_address_p (GET_MODE (x), XEXP (x, 0)))
  1829.       return x;
  1830.  
  1831.     /* Don't replace a value with a more expensive one.  */
  1832.     if (rtx_cost (XEXP (x, 0)) < rtx_cost (newaddr))
  1833.       return x;
  1834.  
  1835.     if (copyflag)
  1836.       return gen_rtx (MEM, GET_MODE (x), newaddr);
  1837.     XEXP (x, 0) = newaddr;
  1838.     return x;
  1839.       }
  1840.     }
  1841.  
  1842.   const_arg0 = 0;
  1843.   const_arg1 = 0;
  1844.   const_arg2 = 0;
  1845.  
  1846.   /* Try folding our operands.
  1847.      Then see which ones have constant values known.  */
  1848.  
  1849.   fmt = GET_RTX_FORMAT (code);
  1850.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1851.     if (fmt[i] == 'e')
  1852.       {
  1853.     register rtx tem = fold_rtx (XEXP (x, i), copyflag);
  1854.  
  1855.     /* If an operand has changed under folding, and we are not supposed to
  1856.        alter the original structure, copy X if we haven't yet done so.  */
  1857.     if (! copied && tem != XEXP (x, i))
  1858.       {
  1859.         int j;
  1860.         rtx new = rtx_alloc (code);
  1861.         PUT_MODE (new, GET_MODE (x));
  1862.         for (j = 0; j < GET_RTX_LENGTH (code); j++)
  1863.           XINT (new, j) = XINT (x, j);
  1864.         x = new;
  1865.         copied = 1;
  1866.       }
  1867.  
  1868.     /* Install the possibly altered folded operand.  */
  1869.     XEXP (x, i) = tem;
  1870.  
  1871.     /* For the first three operands, see if the operand
  1872.        is constant or equivalent to a constant.  */
  1873.     if (i < 3)
  1874.       {
  1875.         rtx const_arg = equiv_constant (tem);
  1876.  
  1877.         switch (i)
  1878.           {
  1879.           case 0:
  1880.         const_arg0 = const_arg;
  1881.         break;
  1882.           case 1:
  1883.         const_arg1 = const_arg;
  1884.         break;
  1885.           case 2:
  1886.         const_arg2 = const_arg;
  1887.         break;
  1888.           }
  1889.       }
  1890.       }
  1891.     else if (fmt[i] == 'E')
  1892.       /* Don't try to fold inside of a vector of expressions.
  1893.      Doing nothing is is harmless.  */
  1894.       ;
  1895.  
  1896.   /* If a commutative operation, place a constant integer as the second
  1897.      operand unless the first operand is also a constant integer.  Otherwise,
  1898.      place any constant second unless the first operand is also a constant.  */
  1899.  
  1900.   switch (code)
  1901.     {
  1902.     case PLUS:
  1903.     case MULT:
  1904.     case UMULT:
  1905.     case AND:
  1906.     case IOR:
  1907.     case XOR:
  1908.     case NE:
  1909.     case EQ:
  1910.       if (const_arg0 && const_arg0 == XEXP (x, 0)
  1911.       && (! (const_arg1 && const_arg1 == XEXP (x, 1))
  1912.           || (GET_CODE (const_arg0) == CONST_INT
  1913.           && GET_CODE (const_arg1) != CONST_INT)))
  1914.     {
  1915.       register rtx tem;
  1916.  
  1917.       if (! copied)
  1918.         copied = 1, x = copy_rtx (x);
  1919.       tem = XEXP (x, 0); XEXP (x, 0) = XEXP (x, 1); XEXP (x, 1) = tem;
  1920.       tem = const_arg0; const_arg0 = const_arg1; const_arg1 = tem;
  1921.     }
  1922.       break;
  1923.     }
  1924.  
  1925.   /* Now decode the kind of rtx X is
  1926.      and then return X (if nothing can be done)
  1927.      or return a folded rtx
  1928.      or store a value in VAL and drop through
  1929.      (to return a CONST_INT for the integer VAL).  */
  1930.  
  1931.   if (GET_RTX_LENGTH (code) == 1)
  1932.     {
  1933.       if (const_arg0 == 0)
  1934.     return x;
  1935.  
  1936.       if (GET_CODE (const_arg0) == CONST_INT)
  1937.     {
  1938.       register int arg0 = INTVAL (const_arg0);
  1939.  
  1940.       switch (GET_CODE (x))
  1941.         {
  1942.         case NOT:
  1943.           val = ~ arg0;
  1944.           break;
  1945.  
  1946.         case NEG:
  1947.           val = - arg0;
  1948.           break;
  1949.  
  1950.         case TRUNCATE:
  1951.           val = arg0;
  1952.           break;
  1953.  
  1954.         case ZERO_EXTEND:
  1955.           {
  1956.         enum machine_mode mode = GET_MODE (XEXP (x, 0));
  1957.         if (mode == VOIDmode)
  1958.           return x;
  1959.         if (GET_MODE_BITSIZE (mode) < HOST_BITS_PER_INT)
  1960.           val = arg0 & ~((-1) << GET_MODE_BITSIZE (mode));
  1961.         else
  1962.           return x;
  1963.         break;
  1964.           }
  1965.  
  1966.         case SIGN_EXTEND:
  1967.           {
  1968.         enum machine_mode mode = GET_MODE (XEXP (x, 0));
  1969.         if (mode == VOIDmode)
  1970.           return x;
  1971.         if (GET_MODE_BITSIZE (mode) < HOST_BITS_PER_INT)
  1972.           {
  1973.             val = arg0 & ~((-1) << GET_MODE_BITSIZE (mode));
  1974.             if (val & (1 << (GET_MODE_BITSIZE (mode) - 1)))
  1975.               val -= 1 << GET_MODE_BITSIZE (mode);
  1976.           }
  1977.         else
  1978.           return x;
  1979.         break;
  1980.           }
  1981.  
  1982.         default:
  1983.           return x;
  1984.         }
  1985.     }
  1986. #if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
  1987.       else if (GET_CODE (const_arg0) == CONST_DOUBLE
  1988.            && GET_CODE (x) == NEG
  1989.            && GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
  1990.     {
  1991.       union real_extract u;
  1992.       register REAL_VALUE_TYPE arg0;
  1993.       jmp_buf handler;
  1994.  
  1995.       if (setjmp (handler))
  1996.         {
  1997.           warning ("floating point trap in constant folding");
  1998.           return x;
  1999.         }
  2000.       set_float_handler (handler);
  2001.       bcopy (&CONST_DOUBLE_LOW (const_arg0), &u, sizeof u);
  2002.       arg0 = u.d;
  2003.  
  2004.       u.d = REAL_VALUE_NEGATE (arg0);
  2005.       x = immed_real_const_1 (u.d, GET_MODE (x));
  2006.       set_float_handler (0);
  2007.       return x;
  2008.     }
  2009. #endif
  2010.       else
  2011.     return x;
  2012.     }
  2013.   else if (GET_RTX_LENGTH (code) == 2)
  2014.     {
  2015.       register int arg0, arg1, arg0s, arg1s;
  2016.       int arithwidth = width;
  2017.  
  2018.       /* If 1st arg is the condition codes, 2nd must be zero
  2019.      and this must be a comparison.
  2020.      Decode the info on how the previous insn set the cc0
  2021.      and use that to deduce result of comparison.  */
  2022.       if (XEXP (x, 0) == cc0_rtx
  2023.       || GET_CODE (XEXP (x, 0)) == COMPARE)
  2024.     {
  2025.       if (XEXP (x, 0) == cc0_rtx)
  2026.         arg0 = prev_insn_cc0;
  2027.       else
  2028.         arg0 = fold_cc0 (VOIDmode, XEXP (x, 0));
  2029.  
  2030.       if (arg0 == 0
  2031.           || const_arg1 != const0_rtx
  2032.           /* 0200 bit in arg0 means only zeroness is known,
  2033.          and sign is not known.  */
  2034.           || ((arg0 & 0200) != 0 && code != EQ && code != NE))
  2035.         return x;
  2036.  
  2037.       /* Extract either the signed or the unsigned digit from ARG0.  */
  2038.       if (code == LEU || code == LTU || code == GEU || code == GTU)
  2039.         arg0 = arg0 & 7;
  2040.       else
  2041.         arg0 = (arg0 >> 3) & 7;
  2042.       if (arg0 == 7) arg0 = -1;
  2043.  
  2044.       switch (code)
  2045.         {
  2046.         case LE:
  2047.         case LEU:
  2048.           return (arg0 <= 0) ? const1_rtx : const0_rtx;
  2049.         case LT:
  2050.         case LTU:
  2051.           return (arg0 < 0) ? const1_rtx : const0_rtx;
  2052.         case GE:
  2053.         case GEU:
  2054.           return (arg0 >= 0) ? const1_rtx : const0_rtx;
  2055.         case GT:
  2056.         case GTU:
  2057.           return (arg0 > 0) ? const1_rtx : const0_rtx;
  2058.         case NE:
  2059. #if defined( DSP56000 )
  2060.         case NEU:
  2061. #endif
  2062.           return (arg0 != 0) ? const1_rtx : const0_rtx;
  2063.         case EQ:
  2064. #if defined( DSP56000 )
  2065.         case EQU:
  2066. #endif
  2067.           return (arg0 == 0) ? const1_rtx : const0_rtx;
  2068.         default:
  2069.           abort ();
  2070.         }
  2071.     }
  2072.  
  2073.       if (const_arg0 == 0 || const_arg1 == 0
  2074.       || GET_CODE (const_arg0) != CONST_INT
  2075.       || GET_CODE (const_arg1) != CONST_INT)
  2076.     {
  2077.       /* Even if we can't compute a constant result,
  2078.          there are some cases worth simplifying.  */
  2079.       /* Note that we cannot rely on constant args to come last,
  2080.          even for commutative operators,
  2081.          because that happens only when the constant is explicit.  */
  2082.       switch (code)
  2083.         {
  2084.         case PLUS:
  2085.           if (const_arg0 == const0_rtx
  2086.           || const_arg0 == fconst0_rtx
  2087.           || const_arg0 == dconst0_rtx)
  2088.         return XEXP (x, 1);
  2089.           if (const_arg1 == const0_rtx
  2090.           || const_arg1 == fconst0_rtx
  2091.           || const_arg1 == dconst0_rtx)
  2092.         return XEXP (x, 0);
  2093.  
  2094.           /* Handle both-operands-constant cases.  */
  2095.           if (const_arg0 != 0 && const_arg1 != 0
  2096.           && GET_CODE (const_arg0) != CONST_DOUBLE
  2097.           && GET_CODE (const_arg1) != CONST_DOUBLE
  2098.           && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT)
  2099.             {
  2100.           if (GET_CODE (const_arg1) == CONST_INT)
  2101.             new = plus_constant (const_arg0, INTVAL (const_arg1));
  2102.           else
  2103.             {
  2104.               new = gen_rtx (PLUS, GET_MODE (x), const0_rtx, const0_rtx);
  2105.               XEXP (new, 0) = const_arg0;
  2106.               if (GET_CODE (const_arg0) == CONST)
  2107.             XEXP (new, 0) = XEXP (const_arg0, 0);
  2108.               XEXP (new, 1) = const_arg1;
  2109.               if (GET_CODE (const_arg1) == CONST)
  2110.             XEXP (new, 1) = XEXP (const_arg1, 0);
  2111.               new = gen_rtx (CONST, GET_MODE (new), new);
  2112.             }
  2113.         }
  2114.           else if (const_arg1 != 0
  2115.                && GET_CODE (const_arg1) == CONST_INT
  2116.                && GET_CODE (XEXP (x, 0)) == PLUS
  2117.                && (CONSTANT_P (XEXP (XEXP (x, 0), 0))
  2118.                || CONSTANT_P (XEXP (XEXP (x, 0), 1))))
  2119.         /* constant + (variable + constant)
  2120.            can result if an index register is made constant.
  2121.            We simplify this by adding the constants.
  2122.            If we did not, it would become an invalid address.  */
  2123.         new = plus_constant (XEXP (x, 0),
  2124.                      INTVAL (const_arg1));
  2125.           break;
  2126.  
  2127.         case COMPARE:
  2128.           if (const_arg1 == const0_rtx)
  2129.         return XEXP (x, 0);
  2130.  
  2131.           if (XEXP (x, 0) == XEXP (x, 1)
  2132.           || (const_arg0 != 0 && const_arg0 == const_arg1))
  2133.         {
  2134.           /* We can't assume x-x is 0 with IEEE floating point.  */
  2135.           if (GET_MODE_CLASS (GET_MODE (x)) == MODE_INT)
  2136.             return const0_rtx;
  2137.         }
  2138.           break;
  2139.           
  2140.         case MINUS:
  2141.           if (const_arg1 == const0_rtx
  2142.           || const_arg1 == fconst0_rtx
  2143.           || const_arg1 == dconst0_rtx)
  2144.         return XEXP (x, 0);
  2145.  
  2146.           if (XEXP (x, 0) == XEXP (x, 1)
  2147.           || (const_arg0 != 0 && const_arg0 == const_arg1))
  2148.         {
  2149.           /* We can't assume x-x is 0 with IEEE floating point.  */
  2150.           if (GET_MODE_CLASS (GET_MODE (x)) == MODE_INT)
  2151.             return const0_rtx;
  2152.         }
  2153.  
  2154.           /* Change subtraction from zero into negation.  */
  2155.           if (const_arg0 == const0_rtx)
  2156.         return gen_rtx (NEG, GET_MODE (x), XEXP (x, 1));
  2157.  
  2158.           /* Don't let a relocatable value get a negative coeff.  */
  2159.           if (const_arg0 != 0 && const_arg1 != 0
  2160.           && GET_CODE (const_arg1) == CONST_INT)
  2161.         new = plus_constant (const_arg0, - INTVAL (const_arg1));
  2162.           break;
  2163.  
  2164.         case MULT:
  2165.         case UMULT:
  2166.           if (const_arg1 && GET_CODE (const_arg1) == CONST_INT
  2167.           && INTVAL (const_arg1) == -1
  2168.           /* Don't do this in the case of widening multiplication.  */
  2169.           && GET_MODE (XEXP (x, 0)) == GET_MODE (x))
  2170.         return gen_rtx (NEG, GET_MODE (x), XEXP (x, 0));
  2171.           if (const_arg0 && GET_CODE (const_arg0) == CONST_INT
  2172.           && INTVAL (const_arg0) == -1
  2173.           && GET_MODE (XEXP (x, 1)) == GET_MODE (x))
  2174.         return gen_rtx (NEG, GET_MODE (x), XEXP (x, 1));
  2175.           if (const_arg1 == const0_rtx || const_arg0 == const0_rtx)
  2176.         new = const0_rtx;
  2177.           if (const_arg1 == fconst0_rtx || const_arg0 == fconst0_rtx)
  2178.         new = fconst0_rtx;
  2179.           if (const_arg1 == dconst0_rtx || const_arg0 == dconst0_rtx)
  2180.         new = dconst0_rtx;
  2181.           if (const_arg1 == const1_rtx)
  2182.         return XEXP (x, 0);
  2183.           if (const_arg0 == const1_rtx)
  2184.         return XEXP (x, 1);
  2185.           break;
  2186.  
  2187.         case IOR:
  2188.           if (const_arg1 == const0_rtx)
  2189.         return XEXP (x, 0);
  2190.           if (const_arg0 == const0_rtx)
  2191.         return XEXP (x, 1);
  2192.           if (const_arg1 && GET_CODE (const_arg1) == CONST_INT
  2193.           && (INTVAL (const_arg1) & GET_MODE_MASK (GET_MODE (x)))
  2194.               == GET_MODE_MASK (GET_MODE (x)))
  2195.         new = const_arg1;
  2196.           if (const_arg0 && GET_CODE (const_arg0) == CONST_INT
  2197.           && (INTVAL (const_arg0) & GET_MODE_MASK (GET_MODE (x)))
  2198.               == GET_MODE_MASK (GET_MODE (x)))
  2199.         new = const_arg0;
  2200.           break;
  2201.  
  2202.         case XOR:
  2203.           if (const_arg1 == const0_rtx)
  2204.         return XEXP (x, 0);
  2205.           if (const_arg0 == const0_rtx)
  2206.         return XEXP (x, 1);
  2207.           if (const_arg1 && GET_CODE (const_arg1) == CONST_INT
  2208.           && (INTVAL (const_arg1) & GET_MODE_MASK (GET_MODE (x)))
  2209.               == GET_MODE_MASK (GET_MODE (x)))
  2210.         return gen_rtx (NOT, GET_MODE (x), XEXP (x, 0));
  2211.           if (const_arg0 && GET_CODE (const_arg0) == CONST_INT
  2212.           && (INTVAL (const_arg0) & GET_MODE_MASK (GET_MODE (x)))
  2213.               == GET_MODE_MASK (GET_MODE (x)))
  2214.         return gen_rtx (NOT, GET_MODE (x), XEXP (x, 1));
  2215.           break;
  2216.  
  2217.         case AND:
  2218.           if (const_arg1 == const0_rtx || const_arg0 == const0_rtx)
  2219.         new = const0_rtx;
  2220.           if (const_arg1 && GET_CODE (const_arg1) == CONST_INT
  2221.           && (INTVAL (const_arg1) & GET_MODE_MASK (GET_MODE (x)))
  2222.               == GET_MODE_MASK (GET_MODE (x)))
  2223.         return XEXP (x, 0);
  2224.           if (const_arg0 && GET_CODE (const_arg0) == CONST_INT
  2225.           && (INTVAL (const_arg0) & GET_MODE_MASK (GET_MODE (x)))
  2226.               == GET_MODE_MASK (GET_MODE (x)))
  2227.         return XEXP (x, 1);
  2228.           break;
  2229.  
  2230.         case DIV:
  2231.         case UDIV:
  2232.           if (const_arg1 == const1_rtx)
  2233.         return XEXP (x, 0);
  2234.           if (const_arg0 == const0_rtx)
  2235.         new = const0_rtx;
  2236.           break;
  2237.  
  2238.         case UMOD:
  2239.         case MOD:
  2240.           if (const_arg0 == const0_rtx || const_arg1 == const1_rtx)
  2241.         new = const0_rtx;
  2242.           break;
  2243.  
  2244.         case LSHIFT:
  2245.         case ASHIFT:
  2246.         case ROTATE:
  2247.         case ASHIFTRT:
  2248.         case LSHIFTRT:
  2249.         case ROTATERT:
  2250.           if (const_arg1 == const0_rtx)
  2251.         return XEXP (x, 0);
  2252.           if (const_arg0 == const0_rtx)
  2253.         new = const_arg0;
  2254.           break;
  2255.         }
  2256.  
  2257.       if (new != 0 && LEGITIMATE_CONSTANT_P (new))
  2258.         return new;
  2259.       return x;
  2260.     }
  2261.  
  2262.       if (arithwidth == 0)
  2263.     {
  2264.       if (GET_MODE (XEXP (x, 0)) != VOIDmode)
  2265.         arithwidth = GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)));
  2266.       if (GET_MODE (XEXP (x, 1)) != VOIDmode)
  2267.         arithwidth = GET_MODE_BITSIZE (GET_MODE (XEXP (x, 1)));
  2268.     }
  2269.  
  2270.       /* Get the integer argument values in two forms:
  2271.      zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S.  */
  2272.  
  2273.       arg0 = INTVAL (const_arg0);
  2274.       arg1 = INTVAL (const_arg1);
  2275.  
  2276.       if (arithwidth < HOST_BITS_PER_INT && arithwidth > 0)
  2277.     {
  2278.       arg0 &= (1 << arithwidth) - 1;
  2279.       arg1 &= (1 << arithwidth) - 1;
  2280.  
  2281.       arg0s = arg0;
  2282.       if (arg0s & (1 << (arithwidth - 1)))
  2283.         arg0s |= ((-1) << arithwidth);
  2284.  
  2285.       arg1s = arg1;
  2286.       if (arg1s & (1 << (arithwidth - 1)))
  2287.         arg1s |= ((-1) << arithwidth);
  2288.     }
  2289.       else
  2290.     {
  2291.       arg0s = arg0;
  2292.       arg1s = arg1;
  2293.     }
  2294.  
  2295.       /* Compute the value of the arithmetic.  */
  2296.  
  2297.       switch (code)
  2298.     {
  2299.     case PLUS:
  2300.       val = arg0 + arg1;
  2301.       break;
  2302.  
  2303.     case MINUS:
  2304.       val = arg0 - arg1;
  2305.       break;
  2306.  
  2307.     case MULT:
  2308.       val = arg0s * arg1s;
  2309.       break;
  2310.  
  2311.     case DIV:
  2312.       if (arg1s == 0)
  2313.         return x;
  2314.       val = arg0s / arg1s;
  2315.       break;
  2316.  
  2317.     case MOD:
  2318.       if (arg1s == 0)
  2319.         return x;
  2320.       val = arg0s % arg1s;
  2321.       break;
  2322.  
  2323.     case UMULT:
  2324.       val = (unsigned) arg0 * arg1;
  2325.       break;
  2326.  
  2327.     case UDIV:
  2328.       if (arg1 == 0)
  2329.         return x;
  2330.       val = (unsigned) arg0 / arg1;
  2331.       break;
  2332.  
  2333.     case UMOD:
  2334.       if (arg1 == 0)
  2335.         return x;
  2336.       val = (unsigned) arg0 % arg1;
  2337.       break;
  2338.  
  2339.     case AND:
  2340.       val = arg0 & arg1;
  2341.       break;
  2342.  
  2343.     case IOR:
  2344.       val = arg0 | arg1;
  2345.       break;
  2346.  
  2347.     case XOR:
  2348.       val = arg0 ^ arg1;
  2349.       break;
  2350.  
  2351.     case NE:
  2352.       val = arg0 != arg1;
  2353.       break;
  2354.  
  2355.     case EQ:
  2356.       val = arg0 == arg1;
  2357.       break;
  2358.  
  2359.     case LE:
  2360.       val = arg0s <= arg1s;
  2361.       break;
  2362.  
  2363.     case LT:
  2364.       val = arg0s < arg1s;
  2365.       break;
  2366.  
  2367.     case GE:
  2368.       val = arg0s >= arg1s;
  2369.       break;
  2370.  
  2371.     case GT:
  2372.       val = arg0s > arg1s;
  2373.       break;
  2374.  
  2375.     case LEU:
  2376.       val = ((unsigned) arg0) <= ((unsigned) arg1);
  2377.       break;
  2378.  
  2379.     case LTU:
  2380.       val = ((unsigned) arg0) < ((unsigned) arg1);
  2381.       break;
  2382.  
  2383.     case GEU:
  2384.       val = ((unsigned) arg0) >= ((unsigned) arg1);
  2385.       break;
  2386.  
  2387.     case GTU:
  2388.       val = ((unsigned) arg0) > ((unsigned) arg1);
  2389.       break;
  2390.  
  2391.     case LSHIFT:
  2392.       /* If target machine uses negative shift counts
  2393.          but host machine does not, simulate them.  */
  2394.       if (arg1 < 0)
  2395.         val = ((unsigned) arg0) >> -arg1;
  2396.       else
  2397.         val = ((unsigned) arg0) << arg1;
  2398.       break;
  2399.  
  2400.     case ASHIFT:
  2401.       if (arg1 < 0)
  2402.         val = arg0s >> -arg1;
  2403.       else
  2404.         val = arg0s << arg1;
  2405.       break;
  2406.  
  2407.     case ROTATERT:
  2408.       arg1 = - arg1;
  2409.     case ROTATE:
  2410.       {
  2411.         int size = GET_MODE_SIZE (GET_MODE (x)) * BITS_PER_UNIT;
  2412.         if (arg1 > 0)
  2413.           {
  2414.         arg1 %= size;
  2415.         val = ((((unsigned) arg0) << arg1)
  2416.                | (((unsigned) arg0) >> (size - arg1)));
  2417.           }
  2418.         else if (arg1 < 0)
  2419.           {
  2420.         arg1 = (- arg1) % size;
  2421.         val = ((((unsigned) arg0) >> arg1)
  2422.                | (((unsigned) arg0) << (size - arg1)));
  2423.           }
  2424.         else
  2425.           val = arg0;
  2426.       }
  2427.       break;
  2428.  
  2429.     case LSHIFTRT:
  2430.       /* If target machine uses negative shift counts
  2431.          but host machine does not, simulate them.  */
  2432.       if (arg1 < 0)
  2433.         val = ((unsigned) arg0) << -arg1;
  2434.       else
  2435.         val = ((unsigned) arg0) >> arg1;
  2436.       break;
  2437.  
  2438.     case ASHIFTRT:
  2439.       if (arg1 < 0)
  2440.         val = arg0s << -arg1;
  2441.       else
  2442.         val = arg0s >> arg1;
  2443.       break;
  2444.  
  2445.     default:
  2446.       return x;
  2447.     }
  2448.     }
  2449.   else if (code == IF_THEN_ELSE && const_arg0 != 0
  2450.        && GET_CODE (const_arg0) == CONST_INT)
  2451.     return XEXP (x, ((INTVAL (const_arg0) != 0) ? 1 : 2));
  2452.   else if (code == IF_THEN_ELSE && XEXP (x, 0) == cc0_rtx
  2453.        && prev_insn_explicit_cc0 != 0)
  2454.     return XEXP (x, ((INTVAL (prev_insn_explicit_cc0) != 0) ? 1 : 2));
  2455.   else if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
  2456.     {
  2457.       if (const_arg0 != 0 && const_arg1 != 0 && const_arg2 != 0
  2458.       && GET_CODE (const_arg0) == CONST_INT
  2459.       && GET_CODE (const_arg1) == CONST_INT
  2460.       && GET_CODE (const_arg2) == CONST_INT)
  2461.     {
  2462.       /* Extracting a bit-field from a constant */
  2463.       val = INTVAL (const_arg0);
  2464. #ifdef BITS_BIG_ENDIAN
  2465.       val >>= (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
  2466.            - INTVAL (const_arg2) - INTVAL (const_arg1));
  2467. #else
  2468.       val >>= INTVAL (const_arg2);
  2469. #endif
  2470.       if (HOST_BITS_PER_INT != INTVAL (const_arg1))
  2471.         {
  2472.           /* First zero-extend.  */
  2473.           val &= (1 << INTVAL (const_arg1)) - 1;
  2474.           /* If desired, propagate sign bit.  */
  2475.           if (code == SIGN_EXTRACT
  2476.           && (val & (1 << (INTVAL (const_arg1) - 1))))
  2477.         val |= ~ (1 << INTVAL (const_arg1));
  2478.         }
  2479.     }
  2480.       else
  2481.     return x;
  2482.     }
  2483.   else
  2484.     return x;
  2485.  
  2486.   /* Clear the bits that don't belong in our mode,
  2487.      unless they and our sign bit are all one.
  2488.      So we get either a reasonable negative value or a reasonable
  2489.      unsigned value for this mode.  */
  2490.   if (width < HOST_BITS_PER_INT && width > 0)
  2491.     {
  2492.       if ((val & ((-1) << (width - 1)))
  2493.       != ((-1) << (width - 1)))
  2494.     val &= (1 << width) - 1;
  2495.     }
  2496.  
  2497.   /* Now make the new constant.  */
  2498.   {
  2499.     rtx new = gen_rtx (CONST_INT, VOIDmode, val);
  2500.     return LEGITIMATE_CONSTANT_P (new) ? new : x;
  2501.   }
  2502. }
  2503.  
  2504. /* Return a constant value currently equivalent to X.
  2505.    Return 0 if we don't know one.  */
  2506.  
  2507. static rtx
  2508. equiv_constant (x)
  2509.      rtx x;
  2510. {
  2511.   rtx tem1;
  2512.  
  2513.   if (CONSTANT_P (x) || GET_CODE (x) == CONST_DOUBLE)
  2514.     return x;
  2515.   else if (GET_CODE (x) == REG
  2516.        && (tem1 = qty_const[reg_qty[REGNO (x)]]) != 0
  2517.        /* Make sure it is really a constant */
  2518.        && GET_CODE (tem1) != REG && GET_CODE (tem1) != PLUS)
  2519.     return tem1;
  2520.   /* If integer truncation is being done with SUBREG,
  2521.      we can compute the result.  */
  2522.   else if (GET_CODE (x) == SUBREG && SUBREG_WORD (x) == 0
  2523.        && (tem1 = qty_const[reg_qty[REGNO (SUBREG_REG (x))]]) != 0
  2524.        /* Make sure it is a known integer.  */
  2525.        && GET_CODE (tem1) == CONST_INT
  2526.        && GET_MODE_SIZE (GET_MODE (x)) <= HOST_BITS_PER_INT
  2527.        /* Make sure this SUBREG is truncation.  */
  2528.        && GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
  2529.     {
  2530.       int value = INTVAL (tem1);
  2531.       if (GET_MODE_BITSIZE (GET_MODE (x)) != HOST_BITS_PER_INT)
  2532.     value &= (1 << GET_MODE_BITSIZE (GET_MODE (x))) - 1;
  2533.  
  2534.       if (value == INTVAL (tem1))
  2535.     return tem1;
  2536.       else
  2537.     return gen_rtx (CONST_INT, VOIDmode, value);
  2538.     }
  2539.   return 0;
  2540. }
  2541.  
  2542. /* Given an expression X which is used to set CC0,
  2543.    return an integer recording (in the encoding used for prev_insn_cc0)
  2544.    how the condition codes would be set by that expression.
  2545.    Return 0 if the value is not constant
  2546.    or if there is any doubt what condition codes result from it.
  2547.  
  2548.    MODE is the machine mode to use to interpret X if it is a CONST_INT.  */
  2549.  
  2550. static int
  2551. fold_cc0 (mode, x)
  2552.      enum machine_mode mode;
  2553.      rtx x;
  2554. {
  2555.   if (GET_CODE (x) == COMPARE)
  2556.     {
  2557.       rtx y0 = fold_rtx (XEXP (x, 0), 0);
  2558.       rtx y1 = fold_rtx (XEXP (x, 1), 0);
  2559.       int u0, u1, s0, s1;
  2560.       enum machine_mode m;
  2561.       rtx tem;
  2562.  
  2563.       m = GET_MODE (y0);
  2564.       if (m == VOIDmode)
  2565.     m = GET_MODE (y1);
  2566.       if (m == VOIDmode)
  2567.     return 0;
  2568.  
  2569.       tem = equiv_constant (y0);
  2570.       if (tem != 0)
  2571.     y0 = tem;
  2572.  
  2573.       if (y0 == 0)
  2574.     return 0;
  2575.  
  2576.       tem = equiv_constant (y1);
  2577.       if (tem != 0)
  2578.     y1 = tem;
  2579.  
  2580.       if (y1 == 0)
  2581.     return 0;
  2582.  
  2583.       /* Compare floats; report the result only for signed compares
  2584.      since that's all there are for floats.  */
  2585.       if (GET_CODE (y0) == CONST_DOUBLE
  2586.       && GET_CODE (y1) == CONST_DOUBLE
  2587.       && GET_MODE_CLASS (GET_MODE (y0)) == MODE_FLOAT)
  2588.     {
  2589.       union real_extract u0, u1;
  2590.       int value;
  2591.       jmp_buf handler;
  2592.  
  2593.       if (setjmp (handler))
  2594.         {
  2595.           warning ("floating point trap in constant folding");
  2596.           return 0;
  2597.         }
  2598.       set_float_handler (handler);
  2599.       bcopy (&CONST_DOUBLE_LOW (y0), &u0, sizeof u0);
  2600.       bcopy (&CONST_DOUBLE_LOW (y1), &u1, sizeof u1);
  2601.       value =  0100 + (REAL_VALUES_LESS (u0.d, u1.d) ? 7 << 3
  2602.                : REAL_VALUES_LESS (u1.d, u0.d) ? 1 << 3 : 0);
  2603.       set_float_handler (0);
  2604.       return value;
  2605.     }
  2606.  
  2607.       /* Aside from that, demand explicit integers.  */
  2608.  
  2609.       if (GET_CODE (y0) != CONST_INT)
  2610.     return 0;
  2611.  
  2612.       if (GET_CODE (y1) != CONST_INT)
  2613.     return 0;
  2614.  
  2615.       s0 = u0 = INTVAL (y0);
  2616.       s1 = u1 = INTVAL (y1);
  2617.  
  2618.       {
  2619.     int width = GET_MODE_BITSIZE (m);
  2620.     if (width < HOST_BITS_PER_INT)
  2621.       {
  2622.         s0 = u0 &= ~ ((-1) << width);
  2623.         s1 = u1 &= ~ ((-1) << width);
  2624.         if (u0 & (1 << (width - 1)))
  2625.           s0 |= ((-1) << width);
  2626.         if (u1 & (1 << (width - 1)))
  2627.           s1 |= ((-1) << width);
  2628.       }
  2629.       }
  2630.  
  2631.       return 0100 + ((s0 < s1 ? 7 : s0 > s1) << 3)
  2632.     + (((unsigned) u0 < (unsigned) u1) ? 7
  2633.        : ((unsigned) u0 > (unsigned) u1));
  2634.     }
  2635.   {
  2636.     rtx y0;
  2637.     int u0, s0;
  2638.     enum machine_mode m;
  2639.  
  2640.     y0 = fold_rtx (x, 0);
  2641.  
  2642.     m = GET_MODE (y0);
  2643.     if (m == VOIDmode)
  2644.       m = mode;
  2645.  
  2646.     if (GET_CODE (y0) == REG)
  2647.       y0 = qty_const[reg_qty[REGNO (y0)]];
  2648.  
  2649.     /* Register had no constant equivalent?  We can't do anything.  */
  2650.     if (y0 == 0)
  2651.       return 0;
  2652.  
  2653.     /* If we don't know the mode, we can't test the sign.  */
  2654.     if (m == VOIDmode)
  2655.       return 0;
  2656.  
  2657.     /* Value is frame-pointer plus a constant?  Or non-explicit constant?
  2658.        That isn't zero, but we don't know its sign.  */
  2659.     if (FIXED_BASE_PLUS_P (y0)
  2660.     || GET_CODE (y0) == SYMBOL_REF || GET_CODE (y0) == CONST
  2661.     || GET_CODE (y0) == LABEL_REF)
  2662.       return 0300 + (1<<3) + 1;
  2663.  
  2664.     /* Otherwise, only integers enable us to optimize.  */
  2665.     if (GET_CODE (y0) != CONST_INT)
  2666.       return 0;
  2667.  
  2668.     s0 = u0 = INTVAL (y0);
  2669.     {
  2670.       int width = GET_MODE_BITSIZE (m);
  2671.       if (width < HOST_BITS_PER_INT)
  2672.     {
  2673.       s0 = u0 &= ~ ((-1) << GET_MODE_BITSIZE (m));
  2674.       if (u0 & (1 << (GET_MODE_BITSIZE (m) - 1)))
  2675.         s0 |= ((-1) << GET_MODE_BITSIZE (m));
  2676.     }
  2677.     }
  2678.     return 0100 + ((s0 < 0 ? 7 : s0 > 0) << 3) + (u0 != 0);
  2679.   }
  2680. }
  2681.  
  2682. /* Attempt to prove that a loop will be executed >= 1 times,
  2683.    or prove it will be executed 0 times.
  2684.    If either can be proved, delete some of the code.  */
  2685.  
  2686. static void
  2687. predecide_loop_entry (insn)
  2688.      register rtx insn;
  2689. {
  2690.   register rtx jump = NEXT_INSN (insn);
  2691.   register rtx p;
  2692.   register rtx loop_top_label = NEXT_INSN (jump);
  2693.   enum anon1 { UNK, DELETE_LOOP, DELETE_JUMP } disposition = UNK;
  2694.   int count = 0;
  2695.  
  2696.   /* Give up if we don't find a jump that enters the loop.  */
  2697.   if (! simplejump_p (jump))
  2698.     return;
  2699.  
  2700.   /* Find the label at the top of the loop.  */
  2701.   while (GET_CODE (loop_top_label) == BARRIER
  2702.      || GET_CODE (loop_top_label) == NOTE)
  2703.     {
  2704.       loop_top_label = NEXT_INSN (loop_top_label);
  2705.       /* No label?  Give up.  */
  2706.       if (loop_top_label == 0)
  2707.     return;
  2708.     }
  2709.   if (GET_CODE (loop_top_label) != CODE_LABEL)
  2710.     abort ();
  2711.  
  2712.   /* Find the label at which the loop is entered.  */
  2713.   p = XEXP (SET_SRC (PATTERN (jump)), 0);
  2714.   if (GET_CODE (p) != CODE_LABEL)
  2715.     abort ();
  2716.  
  2717.   /* Trace the flow of control through the end test,
  2718.      propagating constants, to see if result is determined.  */
  2719.   prev_insn_cc0 = 0;
  2720.   prev_insn_explicit_cc0 = 0;
  2721.   /* Avoid infinite loop if we find a cycle of jumps.  */
  2722.   while (count < 10)
  2723.     {
  2724.       /* At end of function?  Means rtl is inconsistent,
  2725.      but this can happen when stmt.c gets confused
  2726.      by a syntax error.  */
  2727.       if (p == 0)
  2728.     break;
  2729.       /* Arriving at end of loop means endtest will drop out.  */
  2730.       if (GET_CODE (p) == NOTE
  2731.       && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
  2732.     {
  2733.       disposition = DELETE_LOOP;
  2734.       break;
  2735.     }
  2736.       else if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == NOTE)
  2737.     ;
  2738.       /* We only know how to handle two kinds of insns:
  2739.      conditional jumps, and those that set the condition codes. */
  2740.       else if (GET_CODE (p) == INSN && GET_CODE (PATTERN (p)) == SET
  2741.            && SET_DEST (PATTERN (p)) == cc0_rtx)
  2742.     {
  2743.       prev_insn_cc0 = fold_cc0 (GET_MODE (SET_SRC (PATTERN (p))),
  2744.                     copy_rtx (SET_SRC (PATTERN (p))));
  2745.       if (GET_CODE (SET_SRC (PATTERN (p))) == CONST_INT)
  2746.         prev_insn_explicit_cc0 = SET_SRC (PATTERN (p));
  2747.     }
  2748.       else if (GET_CODE (p) == JUMP_INSN
  2749.            && GET_CODE (PATTERN (p)) == SET
  2750.            && SET_DEST (PATTERN (p)) == pc_rtx)
  2751.     {
  2752.       register rtx target
  2753.         = fold_rtx (SET_SRC (PATTERN (p)), 1);
  2754.       if (GET_CODE (target) == LABEL_REF)
  2755.         p = XEXP (target, 0);
  2756.       else if (target != pc_rtx)
  2757.         /* If destination of jump is not fixed, give up.  */
  2758.         break;
  2759.       count++;
  2760.     }
  2761.       /* Any other kind of insn means we don't know
  2762.      what result the test will have.  */
  2763.       else
  2764.     break;
  2765.  
  2766.       /* Arriving at top of loop means we can drop straight in.
  2767.      Check here because we can arrive only via a jump insn
  2768.      which would have changed P above.  */
  2769.       if (p == loop_top_label)
  2770.     {
  2771.       disposition = DELETE_JUMP;
  2772.       break;
  2773.     }
  2774.       /* We went past one insn; consider the next.  */
  2775.       p = NEXT_INSN (p);
  2776.     }
  2777.   if (disposition == DELETE_JUMP)
  2778.     {
  2779.       /* We know the loop test will succeed the first time,
  2780.      so delete the jump to the test; drop right into loop.
  2781.      Note that one call to delete_insn gets the BARRIER as well.  */
  2782.       delete_insn (jump);
  2783.     }
  2784.   if (disposition == DELETE_LOOP)
  2785.     {
  2786.       /* We know the endtest will fail and drop right out of the loop,
  2787.      but it isn't safe to delete the loop here.
  2788.      There could be jumps into it from outside.
  2789.      So make the entry-jump jump around the loop.
  2790.      This will cause find_basic_blocks to delete it if appropriate.  */
  2791.       register rtx label = gen_label_rtx ();
  2792.       emit_label_after (label, p);
  2793.       redirect_jump (jump, label);
  2794.     }
  2795. }
  2796.  
  2797. /* CSE processing for one instruction.
  2798.    First simplify sources and addresses of all assignments
  2799.    in the instruction, using previously-computed equivalents values.
  2800.    Then install the new sources and destinations in the table
  2801.    of available values.  */
  2802.  
  2803. /* Data on one SET contained in the instruction.  */
  2804.  
  2805. struct set
  2806. {
  2807.   /* The SET rtx itself.  */
  2808.   rtx rtl;
  2809.   /* The hash-table element for the SET_SRC of the SET.  */
  2810.   struct table_elt *src_elt;
  2811.   /* Hash code for the SET_SRC.  */
  2812.   int src_hash_code;
  2813.   /* Hash code for the SET_DEST.  */
  2814.   int dest_hash_code;
  2815.   /* The SET_DEST, with SUBREG, etc., stripped.  */
  2816.   rtx inner_dest;
  2817.   /* Place where the pointer to the INNER_DEST was found.  */
  2818.   rtx *inner_dest_loc;
  2819.   /* Nonzero if the SET_SRC is in memory.  */ 
  2820.   char src_in_memory;
  2821.   /* Nonzero if the SET_SRC is in a structure.  */ 
  2822.   char src_in_struct;
  2823.   /* Nonzero if the SET_SRC contains something
  2824.      whose value cannot be predicted and understood.  */
  2825.   char src_volatile;
  2826.   /* Original machine mode, in case it becomes a CONST_INT.  */
  2827.   enum machine_mode mode;
  2828. };
  2829.  
  2830. static void
  2831. cse_insn (insn)
  2832.      rtx insn;
  2833. {
  2834.   register rtx x = PATTERN (insn);
  2835.   register int i;
  2836.   register int n_sets = 0;
  2837.  
  2838. #if defined ( DSP56000 ) || defined ( DSP96000 ) || defined ( DSP56100 )
  2839.   /* sometimes this cse pass takes an insn created by a gen_ function and
  2840.      transforms it so that no define_insn will match it. we'll keep a copy
  2841.      of the original pattern. if, after the transformation, the insn no
  2842.      longer matches, then we'll slam the old pattern back in and live with
  2843.      it. */
  2844.   rtx original_pattern = copy_rtx ( PATTERN ( insn ));
  2845. #endif  
  2846.   /* Records what this insn does to set CC0,
  2847.      using same encoding used for prev_insn_cc0.  */
  2848.   int this_insn_cc0 = 0;
  2849.   /* Likewise, what to store in prev_insn_explicit_cc0.  */
  2850.   rtx this_insn_explicit_cc0 = 0;
  2851.   struct write_data writes_memory;
  2852.   static struct write_data init = {0, 0, 0};
  2853.  
  2854.   rtx src_eqv = 0;
  2855.   struct table_elt *src_eqv_elt = 0;
  2856.   int src_eqv_in_memory;
  2857.   int src_eqv_in_struct;
  2858.   int src_eqv_hash_code;
  2859.  
  2860.   struct set *sets;
  2861.  
  2862.   this_insn = insn;
  2863.   writes_memory = init;
  2864.  
  2865.   /* Find all the SETs and CLOBBERs in this instruction.
  2866.      Record all the SETs in the array `set' and count them.
  2867.      Also determine whether there is a CLOBBER that invalidates
  2868.      all memory references, or all references at varying addresses.  */
  2869.  
  2870.   if (GET_CODE (x) == SET)
  2871.     {
  2872.       rtx tem;
  2873.       n_sets = 1;
  2874.       sets = (struct set *) alloca (sizeof (struct set));
  2875.       sets[0].rtl = x;
  2876.  
  2877.       if (REG_NOTES (insn) != 0)
  2878.     {
  2879.       /* Store the equivalent value (re REG_EQUAL or REG_EQUIV) in SRC_EQV.  */
  2880.       tem = find_reg_note (insn, REG_EQUIV, 0);
  2881.       if (tem == 0)
  2882.         tem = find_reg_note (insn, REG_EQUAL, 0);
  2883.       if (tem) src_eqv = XEXP (tem, 0);
  2884.  
  2885.       /* Ignore the REG_EQUAL or REG_EQUIV note if its contents
  2886.          are the same as the source.  */
  2887.       if (src_eqv && rtx_equal_p (src_eqv, SET_SRC (x)))
  2888.         src_eqv = 0;
  2889.     }
  2890.  
  2891.       /* Return now for unconditional jumps.
  2892.      They never need cse processing, so this does not hurt.
  2893.      The reason is not efficiency but rather
  2894.      so that we can test at the end for instructions
  2895.      that have been simplified to unconditional jumps
  2896.      and not be misled by unchanged instructions
  2897.      that were unconditional jumps to begin with.  */
  2898.       if (SET_DEST (x) == pc_rtx
  2899.       && GET_CODE (SET_SRC (x)) == LABEL_REF)
  2900.     return;
  2901.  
  2902.       /* Return now for call-insns, (set (reg 0) (call ...)).
  2903.      The hard function value register is used only once, to copy to
  2904.      someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)! */
  2905.       if (GET_CODE (SET_SRC (x)) == CALL)
  2906.     {
  2907.       canon_reg (SET_SRC (x));
  2908. #if defined ( DSP56000 ) || defined ( DSP96000 ) || defined ( DSP56100 )
  2909.       /* make sure the mangled insn matches. */
  2910.       { 
  2911.           enum rtx_code code = GET_CODE ( insn );
  2912.           
  2913.           if (( INSN == code || JUMP_INSN == code || CALL_INSN == code ) &&
  2914.           ( 0 > asm_noperands ( PATTERN ( insn ))))
  2915.           {
  2916.           INSN_CODE ( insn ) = -1;
  2917.           if ( -1 == recog_memoized ( insn ))
  2918.           {
  2919.               PATTERN ( insn ) = original_pattern;
  2920.               (void) recog_memoized ( );
  2921.           }
  2922.           INSN_CODE ( insn ) = -1;
  2923.           }
  2924.       }
  2925. #endif
  2926.       return;
  2927.     }
  2928.     }
  2929.   else if (GET_CODE (x) == PARALLEL)
  2930.     {
  2931.       register int lim = XVECLEN (x, 0);
  2932.  
  2933.       sets = (struct set *) alloca (lim * sizeof (struct set));
  2934.  
  2935.       /* Find all regs explicitly clobbered in this insn,
  2936.      and ensure they are not replaced with any other regs
  2937.      elsewhere in this insn.
  2938.      When a reg that is clobbered is also used for input,
  2939.      we should presume that that is for a reason,
  2940.      and we should not substitute some other register
  2941.      which is not supposed to be clobbered.  */
  2942.       for (i = 0; i < lim; i++)
  2943.     {
  2944.       register rtx y = XVECEXP (x, 0, i);
  2945.       if (GET_CODE (y) == CLOBBER && GET_CODE (XEXP (y, 0)) == REG)
  2946.         invalidate (XEXP (y, 0));
  2947.     }
  2948.         
  2949.       for (i = 0; i < lim; i++)
  2950.     {
  2951.       register rtx y = XVECEXP (x, 0, i);
  2952.       if (GET_CODE (y) == SET)
  2953.         sets[n_sets++].rtl = y;
  2954.       else if (GET_CODE (y) == CLOBBER)
  2955.         {
  2956.           /* If we clobber memory, take note of that,
  2957.          and canon the address.
  2958.          This does nothing when a register is clobbered
  2959.          because we have already invalidated the reg.  */
  2960.           canon_reg (y);
  2961.           note_mem_written (XEXP (y, 0), &writes_memory);
  2962.         }
  2963.       else if (GET_CODE (y) == USE
  2964.            && ! (GET_CODE (XEXP (y, 0)) == REG
  2965.              && REGNO (XEXP (y, 0)) < FIRST_PSEUDO_REGISTER))
  2966.         canon_reg (y);
  2967.       else if (GET_CODE (y) == CALL)
  2968.         canon_reg (y);
  2969.     }
  2970.     }
  2971.   else if (GET_CODE (x) == CLOBBER)
  2972.     note_mem_written (XEXP (x, 0), &writes_memory);
  2973.   else if (GET_CODE (x) == CALL)
  2974.     canon_reg (x);
  2975.  
  2976.   if (n_sets == 0)
  2977.     {
  2978.       invalidate_from_clobbers (&writes_memory, x);
  2979. #if defined ( DSP56000 ) || defined ( DSP96000 ) || defined ( DSP56100 )
  2980.       /* make sure the mangled insn matches. */
  2981.       { 
  2982.       enum rtx_code code = GET_CODE ( insn );
  2983.       
  2984.       if (( INSN == code || JUMP_INSN == code || CALL_INSN == code ) &&
  2985.           ( 0 > asm_noperands ( PATTERN ( insn ))))
  2986.       {
  2987.           INSN_CODE ( insn ) = -1;
  2988.           if ( -1 == recog_memoized ( insn ))
  2989.           {
  2990.           PATTERN ( insn ) = original_pattern;
  2991.           (void) recog_memoized ( insn );
  2992.           }
  2993.           INSN_CODE ( insn ) = -1;
  2994.       }
  2995.       }
  2996. #endif  
  2997.       return;
  2998.     }
  2999.  
  3000.   /* Canonicalize sources and addresses of destinations.
  3001.      set sets[i].src_elt to the class each source belongs to.
  3002.      Detect assignments from or to volatile things
  3003.      and set set[i] to zero so they will be ignored
  3004.      in the rest of this function.
  3005.  
  3006.      Nothing in this loop changes the hash table or the register chains.  */
  3007.  
  3008.   for (i = 0; i < n_sets; i++)
  3009.     {
  3010.       register rtx src, dest;
  3011.       register struct table_elt *elt;
  3012.       enum machine_mode mode;
  3013.  
  3014.       dest = SET_DEST (sets[i].rtl);
  3015.       src = SET_SRC (sets[i].rtl);
  3016.  
  3017.       /* If SRC is a constant that has no machine mode,
  3018.      hash it with the destination's machine mode.
  3019.      This way we can keep different modes separate.  */
  3020.  
  3021.       mode = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
  3022.       sets[i].mode = mode;
  3023.  
  3024.       /* Replace each registers in SRC with oldest equivalent register,
  3025.      but if DEST is a register do not replace it if it appears in SRC.  */
  3026.  
  3027.       if (GET_CODE (dest) == REG)
  3028.     {
  3029.       int tem = reg_qty[REGNO (dest)];
  3030.       reg_qty[REGNO (dest)] = REGNO (dest);
  3031.       src = canon_reg (src);
  3032.  
  3033.       if (src_eqv)
  3034.         src_eqv = canon_reg (src_eqv);
  3035.  
  3036.       reg_qty[REGNO (dest)] = tem;
  3037.     }
  3038.       else
  3039.     {
  3040.       src = canon_reg (src);
  3041.  
  3042.       if (src_eqv)
  3043.         src_eqv = canon_reg (src_eqv);
  3044.     }
  3045.  
  3046.       if (src_eqv)
  3047.     {
  3048.       enum machine_mode eqvmode = mode;
  3049.       if (GET_CODE (dest) == STRICT_LOW_PART)
  3050.         eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
  3051.       do_not_record = 0;
  3052.       hash_arg_in_memory = 0;
  3053.       hash_arg_in_struct = 0;
  3054.       src_eqv = fold_rtx (src_eqv, 0);
  3055.       src_eqv_hash_code = HASH (src_eqv, eqvmode);
  3056.  
  3057.       /* Replace the src_eqv with its cheapest equivalent.  */
  3058.  
  3059.       if (!do_not_record)
  3060.         {
  3061.           elt = lookup (src_eqv, src_eqv_hash_code, eqvmode);
  3062.           if (elt && elt != elt->first_same_value)
  3063.         {
  3064.           elt = elt->first_same_value;
  3065.           /* Find the cheapest one that is still valid.  */
  3066.           while ((GET_CODE (elt->exp) != REG
  3067.               && !exp_equiv_p (elt->exp, elt->exp, 1))
  3068.              || elt->equivalence_only)
  3069.             elt = elt->next_same_value;
  3070.           src_eqv = copy_rtx (elt->exp);
  3071.           hash_arg_in_memory = 0;
  3072.           hash_arg_in_struct = 0;
  3073.           src_eqv_hash_code = HASH (src_eqv, elt->mode);
  3074.         }
  3075.           src_eqv_elt = elt;
  3076.         }
  3077.       else
  3078.         src_eqv = 0;
  3079.  
  3080.       src_eqv_in_memory = hash_arg_in_memory;
  3081.       src_eqv_in_struct = hash_arg_in_struct;
  3082.     }
  3083.  
  3084.       /* Compute SRC's hash code, and also notice if it
  3085.      should not be recorded at all.  In that case,
  3086.      prevent any further processing of this assignment.  */
  3087.       do_not_record = 0;
  3088.       hash_arg_in_memory = 0;
  3089.       hash_arg_in_struct = 0;
  3090.       src = fold_rtx (src, 0);
  3091.       /* If SRC is a subreg of a reg with a known value,
  3092.      perform the truncation now.  */
  3093.       if (GET_CODE (src) == SUBREG)
  3094.     {
  3095.       rtx temp = equiv_constant (src);
  3096.       if (temp)
  3097.         src = temp;
  3098.     }
  3099.       /* If we have (NOT Y), see if Y is known to be (NOT Z).
  3100.      If so, (NOT Y) simplifies to Z.  */
  3101.       if (GET_CODE (src) == NOT || GET_CODE (src) == NEG)
  3102.     {
  3103.       rtx y = lookup_as_function (XEXP (src, 0), GET_CODE (src));
  3104.       if (y != 0)
  3105.         src = copy_rtx (XEXP (y, 0));
  3106.     }
  3107.  
  3108.       /* If storing a constant value in a register that
  3109.      previously held the constant value 0,
  3110.      record this fact with a REG_WAS_0 note on this insn.  */
  3111.       if (GET_CODE (src) == CONST_INT
  3112.       && GET_CODE (dest) == REG
  3113.       && qty_const[reg_qty[REGNO (dest)]] == const0_rtx)
  3114.     REG_NOTES (insn) = gen_rtx (INSN_LIST, REG_WAS_0,
  3115.                     qty_const_insn[reg_qty[REGNO (dest)]],
  3116.                     REG_NOTES (insn));
  3117.  
  3118.       sets[i].src_hash_code = HASH (src, mode);
  3119.  
  3120.       sets[i].src_volatile = do_not_record;
  3121.  
  3122. #if 0
  3123.       /* This code caused multiple hash-table entries
  3124.      to be created for registers.  Invalidation
  3125.      would only get one, leaving others that didn't belong.
  3126.      I don't know what good this ever did.  */
  3127.       if (GET_CODE (src) == REG)
  3128.     {
  3129.       sets[i].src_in_memory = 0;
  3130.       sets[i].src_elt = 0;
  3131.     }
  3132.       else ...;
  3133. #endif
  3134.       /* If source is a perverse subreg (such as QI treated as an SI),
  3135.      treat it as volatile.  It may do the work of an SI in one context
  3136.      where the extra bits are not being used, but cannot replace an SI
  3137.      in general.  */
  3138.       if (GET_CODE (src) == SUBREG
  3139.       && (GET_MODE_SIZE (GET_MODE (src))
  3140.           > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
  3141.     sets[i].src_volatile = 1;
  3142.       else if (!sets[i].src_volatile)
  3143.     {
  3144.       /* Replace the source with its cheapest equivalent.  */
  3145.  
  3146.       elt = lookup (src, sets[i].src_hash_code, mode);
  3147.       if (elt && elt != elt->first_same_value)
  3148.         {
  3149.           elt = elt->first_same_value;
  3150.           /* Find the cheapest one that is still valid.  */
  3151.           while ((GET_CODE (elt->exp) != REG
  3152.               && !exp_equiv_p (elt->exp, elt->exp, 1))
  3153.              || elt->equivalence_only)
  3154.         elt = elt->next_same_value;
  3155.           src = copy_rtx (elt->exp);
  3156.           hash_arg_in_memory = 0;
  3157.           hash_arg_in_struct = 0;
  3158.           sets[i].src_hash_code = HASH (src, elt->mode);
  3159.         }
  3160.  
  3161.       /* If ELT is a constant, is there a register
  3162.          linearly related to it?  If so, replace it
  3163.          with the sum of that register plus an offset.  */
  3164.  
  3165.       if (GET_CODE (src) == CONST && n_sets == 1
  3166.           && SET_DEST (sets[i].rtl) != cc0_rtx)
  3167.         {
  3168.           rtx newsrc = use_related_value (src, elt);
  3169.           if (newsrc == 0 && src_eqv != 0)
  3170.         newsrc = use_related_value (src_eqv, src_eqv_elt);
  3171.           if (newsrc)
  3172.         {
  3173.           rtx oldsrc = src;
  3174.           src = newsrc;
  3175.           hash_arg_in_memory = 0;
  3176.           hash_arg_in_struct = 0;
  3177.           sets[i].src_hash_code = HASH (src, GET_MODE (src));
  3178.           /* The new expression for the SRC has the same value
  3179.              as the previous one; so if the previous one is in
  3180.              the hash table, put the new one in as equivalent.  */
  3181.           if (elt != 0)
  3182.             elt = insert (src, elt->first_same_value, sets[i].src_hash_code,
  3183.                   elt->mode);
  3184.           else
  3185.             {
  3186.               /* Maybe the new expression is in the table already.  */
  3187.               elt = lookup (src, sets[i].src_hash_code, mode);
  3188.               /* And maybe a register contains the same value.  */
  3189.               if (elt && elt != elt->first_same_value)
  3190.             {
  3191.               elt = elt->first_same_value;
  3192.               /* Find the cheapest one that is still valid.  */
  3193.               while ((GET_CODE (elt->exp) != REG
  3194.                   && !exp_equiv_p (elt->exp, elt->exp, 1))
  3195.                  || elt->equivalence_only)
  3196.                 elt = elt->next_same_value;
  3197.               src = copy_rtx (elt->exp);
  3198.               hash_arg_in_memory = 0;
  3199.               hash_arg_in_struct = 0;
  3200.               sets[i].src_hash_code = HASH (src, elt->mode);
  3201.             }
  3202.             }
  3203.  
  3204.           /* This would normally be inhibited by the REG_EQUIV
  3205.              note we are about to make.  */
  3206. #if 0
  3207.           /* Deleted because the inhibition was deleted.  */
  3208.           SET_SRC (sets[i].rtl) = src;
  3209. #endif
  3210.  
  3211.           /* Record the actual constant value in a REG_EQUIV note.  */
  3212.           if (GET_CODE (SET_DEST (sets[i].rtl)) == REG)
  3213.             REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_EQUIV,
  3214.                         oldsrc, REG_NOTES (insn));
  3215.         }
  3216.         }
  3217.  
  3218.       sets[i].src_elt = elt;
  3219.       sets[i].src_in_memory = hash_arg_in_memory;
  3220.       sets[i].src_in_struct = hash_arg_in_struct;
  3221.     }
  3222.  
  3223.       /* Either canon_reg or the copy_rtx may have changed this.  */
  3224.       /* Note it is not safe to replace the sources if there
  3225.      is more than one set.  We could get an insn
  3226.      [(set (reg) (reg)) (set (reg) (reg))], which is probably
  3227.      not in the machine description.
  3228.      This case we could handle by breaking into several insns.
  3229.      Cases of partial substitution cannot win at all.  */
  3230.       /* Also, if this insn is setting a "constant" register,
  3231.      we may not replace the value that is given to it.  */
  3232.       if (n_sets == 1)
  3233. #if 0
  3234.     /* Now that the REG_EQUIV contains the constant instead of the reg,
  3235.        it should be ok to modify the insn's actual source.  */
  3236.     if (REG_NOTES (insn) == 0
  3237.         || REG_NOTE_KIND (REG_NOTES (insn)) != REG_EQUIV)
  3238. #endif
  3239.       SET_SRC (sets[0].rtl) = src;
  3240.  
  3241.       do_not_record = 0;
  3242.       sets[i].inner_dest_loc = &SET_DEST (sets[0].rtl);
  3243.  
  3244.       /* Look within any SIGN_EXTRACT or ZERO_EXTRACT
  3245.      to the MEM or REG within it.  */
  3246.       while (1)
  3247.     {
  3248.       if (GET_CODE (dest) == SIGN_EXTRACT
  3249.           || GET_CODE (dest) == ZERO_EXTRACT)
  3250.         {
  3251.           XEXP (dest, 1) = canon_reg (XEXP (dest, 1));
  3252.           XEXP (dest, 2) = canon_reg (XEXP (dest, 2));
  3253.           sets[i].inner_dest_loc = &XEXP (dest, 0);
  3254.           dest = XEXP (dest, 0);
  3255.         }
  3256.       else if (GET_CODE (dest) == SUBREG
  3257.            || GET_CODE (dest) == STRICT_LOW_PART)
  3258.         {
  3259.           sets[i].inner_dest_loc = &XEXP (dest, 0);
  3260.           dest = XEXP (dest, 0);
  3261.         }
  3262.       else
  3263.         break;
  3264.     }
  3265.  
  3266.       sets[i].inner_dest = dest;
  3267.  
  3268.       /* If storing into memory, do cse on the memory address.
  3269.      Also compute the hash code of the destination now,
  3270.      before the effects of this instruction are recorded,
  3271.      since the register values used in the address computation
  3272.      are those before this instruction.  */
  3273.       if (GET_CODE (dest) == MEM)
  3274.     {
  3275.       register rtx addr;
  3276.       register int hash;
  3277.  
  3278.       canon_reg (dest);
  3279.       dest = fold_rtx (dest, 0);
  3280.       addr = XEXP (dest, 0);
  3281.  
  3282.       /* Pushing or popping does not invalidate anything.  */
  3283.       if ((GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC
  3284.            || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC)
  3285.           && GET_CODE (XEXP (addr, 0)) == REG
  3286.           && REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
  3287.         ;
  3288.       else
  3289.         /* Otherwise, decide whether we invalidate
  3290.            everything in memory, or just things at non-fixed places.
  3291.            Writing a large aggregate must invalidate everything
  3292.            because we don't know how long it is.  */
  3293.         note_mem_written (dest, &writes_memory);
  3294.  
  3295.       /* Do not try to replace addresses of local and argument slots.
  3296.          The MEM expressions for args and non-register local variables
  3297.          are made only once and inserted in many instructions,
  3298.          as well as being used to control symbol table output.
  3299.          It is not safe to clobber them.  It also doesn't do any good!  */
  3300.       if ((GET_CODE (addr) == PLUS
  3301.            && GET_CODE (XEXP (addr, 0)) == REG
  3302.            && GET_CODE (XEXP (addr, 1)) == CONST_INT
  3303.            && (hash = REGNO (XEXP (addr, 0)),
  3304.            hash == FRAME_POINTER_REGNUM || hash == ARG_POINTER_REGNUM))
  3305.           || (GET_CODE (addr) == REG
  3306.           && (hash = REGNO (addr),
  3307.               hash == FRAME_POINTER_REGNUM || hash == ARG_POINTER_REGNUM)))
  3308.         sets[i].dest_hash_code = ((int)MEM + canon_hash (addr, GET_MODE (dest))) % NBUCKETS;
  3309.       else
  3310.         {
  3311.           /* Look for a simpler equivalent for the destination address.  */
  3312.           hash = HASH (addr, Pmode);
  3313.           if (! do_not_record)
  3314.         {
  3315.           elt = lookup (addr, hash, Pmode);
  3316.           sets[i].dest_hash_code = ((int) MEM + hash) % NBUCKETS;
  3317.  
  3318.           if (elt && elt != elt->first_same_value)
  3319.             {
  3320.               elt = elt->first_same_value;
  3321.               /* Find the cheapest one that is still valid.  */
  3322.               while ((GET_CODE (elt->exp) != REG
  3323.                   && !exp_equiv_p (elt->exp, elt->exp, 1))
  3324.                  || elt->equivalence_only)
  3325.             elt = elt->next_same_value;
  3326.  
  3327.               addr = copy_rtx (elt->exp);
  3328.               /* Create a new MEM rtx, in case the old one
  3329.              is shared somewhere else.  */
  3330.               dest = gen_rtx (MEM, GET_MODE (dest), addr);
  3331.               MEM_VOLATILE_P (dest)
  3332.             = MEM_VOLATILE_P (sets[i].inner_dest);
  3333.               MEM_IN_STRUCT_P (dest)
  3334.             = MEM_IN_STRUCT_P (sets[i].inner_dest);
  3335.               *sets[i].inner_dest_loc = dest;
  3336.               sets[i].inner_dest = dest;
  3337.             }
  3338.         }
  3339.         }
  3340.     }
  3341.  
  3342.       /* Don't enter a bit-field in the hash table
  3343.      because the value in it after the store
  3344.      may not equal what was stored, due to truncation.  */
  3345.  
  3346.       if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT
  3347.       || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT)
  3348.     {
  3349.       rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
  3350.       rtx value = equiv_constant (SET_SRC (sets[i].rtl));
  3351.  
  3352.       if (value != 0 && GET_CODE (value) == CONST_INT
  3353.           && GET_CODE (width) == CONST_INT
  3354.           && INTVAL (width) < HOST_BITS_PER_INT
  3355.           && ! (INTVAL (value) & (-1) << INTVAL (width)))
  3356.         /* Exception: if the value is constant,
  3357.            we can tell whether truncation would change it.  */
  3358.         ;
  3359.       else
  3360.         sets[i].src_volatile = 1, src_eqv = 0;
  3361.     }
  3362.  
  3363.       /* No further processing for this assignment
  3364.      if destination is volatile or if the source and destination
  3365.      are the same.  */
  3366.  
  3367.       else if (do_not_record
  3368.            || (GET_CODE (dest) == REG 
  3369.            ? REGNO (dest) == STACK_POINTER_REGNUM
  3370.            : GET_CODE (dest) != MEM)
  3371.            || rtx_equal_p (SET_SRC (sets[i].rtl), SET_DEST (sets[i].rtl)))
  3372.     sets[i].rtl = 0;
  3373.  
  3374.       if (sets[i].rtl != 0 && dest != SET_DEST (sets[i].rtl))
  3375.     sets[i].dest_hash_code = HASH (SET_DEST (sets[i].rtl), mode);
  3376.  
  3377.       if (dest == cc0_rtx
  3378.       && (GET_CODE (src) == COMPARE
  3379.           || CONSTANT_P (src)
  3380.           || GET_CODE (src) == REG))
  3381.     this_insn_cc0 = fold_cc0 (sets[i].mode, src);
  3382.  
  3383.       if (dest == cc0_rtx && GET_CODE (src) == CONST_INT)
  3384.     this_insn_explicit_cc0 = src;
  3385.     }
  3386.  
  3387.   /* Now enter all non-volatile source expressions in the hash table
  3388.      if they are not already present.
  3389.      Record in src_elt the heads of their equivalence classes.
  3390.      This way we can insert the corresponding destinations into
  3391.      the same classes even if the actual sources are no longer in them
  3392.      (having been invalidated).  */
  3393.  
  3394.   if (src_eqv && src_eqv_elt == 0 && sets[0].rtl != 0)
  3395.     {
  3396.       register struct table_elt *elt;
  3397.       rtx dest = SET_DEST (sets[0].rtl);
  3398.       enum machine_mode eqvmode = GET_MODE (dest);
  3399.  
  3400.       if (GET_CODE (dest) == STRICT_LOW_PART)
  3401.     eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
  3402.       if (insert_regs (src_eqv, 0, 0))
  3403.     src_eqv_hash_code = HASH (src_eqv, eqvmode);
  3404.       elt = insert (src_eqv, 0, src_eqv_hash_code, eqvmode);
  3405.       elt->in_memory = src_eqv_in_memory;
  3406.       elt->in_struct = src_eqv_in_struct;
  3407.       elt->equivalence_only = 1;
  3408.       src_eqv_elt = elt->first_same_value;
  3409.     }
  3410.  
  3411.   for (i = 0; i < n_sets; i++)
  3412.     if (sets[i].rtl && ! sets[i].src_volatile)
  3413.       {
  3414.     if (GET_CODE (SET_DEST (sets[i].rtl)) == STRICT_LOW_PART)
  3415.       {
  3416.         /* REG_EQUAL in setting a STRICT_LOW_PART
  3417.            gives an equivalent for the entire destination register,
  3418.            not just for the subreg being stored in now.
  3419.            This is a more interesting equivalent, so we arrange later
  3420.            to treat the entire reg as the destination.  */
  3421.         sets[i].src_elt = src_eqv_elt;
  3422.         sets[i].src_hash_code = src_eqv_hash_code;
  3423.       }
  3424.     else if (sets[i].src_elt == 0)
  3425.       {
  3426.         register rtx src = SET_SRC (sets[i].rtl);
  3427.         register rtx dest = SET_DEST (sets[i].rtl);
  3428.         register struct table_elt *elt;
  3429.         enum machine_mode mode
  3430.           = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
  3431.  
  3432.         /* Note that these insert_regs calls cannot remove
  3433.            any of the src_elt's, because they would have failed to match
  3434.            if not still valid.  */
  3435.         if (insert_regs (src, 0, 0))
  3436.           sets[i].src_hash_code = HASH (src, mode);
  3437.         elt = insert (src, src_eqv_elt, sets[i].src_hash_code, mode);
  3438.         elt->in_memory = sets[i].src_in_memory;
  3439.         elt->in_struct = sets[i].src_in_struct;
  3440.         sets[i].src_elt = elt->first_same_value;
  3441.       }
  3442.       }
  3443.  
  3444.   invalidate_from_clobbers (&writes_memory, x);
  3445.  
  3446.   /* Now invalidate everything set by this instruction.
  3447.      If a SUBREG or other funny destination is being set,
  3448.      sets[i].rtl is still nonzero, so here we invalidate the reg
  3449.      a part of which is being set.  */
  3450.  
  3451.   for (i = 0; i < n_sets; i++)
  3452.     if (sets[i].rtl)
  3453.       {
  3454.     register rtx dest = sets[i].inner_dest;
  3455.  
  3456.     /* Needed for registers to remove the register from its
  3457.        previous quantity's chain.
  3458.        Needed for memory if this is a nonvarying address, unless
  3459.        we have just done an invalidate_memory that covers even those.  */
  3460.     if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG
  3461.         || (! writes_memory.all && ! cse_rtx_addr_varies_p (dest)))
  3462.       invalidate (dest);
  3463.       }
  3464.  
  3465.   /* Make sure registers mentioned in destinations
  3466.      are safe for use in an expression to be inserted.
  3467.      This removes from the hash table
  3468.      any invalid entry that refers to one of these registers.  */
  3469.  
  3470.   for (i = 0; i < n_sets; i++)
  3471.     if (sets[i].rtl && GET_CODE (SET_DEST (sets[i].rtl)) != REG)
  3472.       mention_regs (SET_DEST (sets[i].rtl));
  3473.  
  3474.   /* We may have just removed some of the src_elt's from the hash table.
  3475.      So replace each one with the current head of the same class.  */
  3476.  
  3477.   for (i = 0; i < n_sets; i++)
  3478.     if (sets[i].rtl)
  3479.       {
  3480.     /* If the source is volatile, its destination goes in
  3481.        a class of its own.  */
  3482.     if (sets[i].src_volatile)
  3483.       sets[i].src_elt = 0;
  3484.  
  3485.     if (sets[i].src_elt && sets[i].src_elt->first_same_value == 0)
  3486.       /* If elt was removed, find current head of same class,
  3487.          or 0 if nothing remains of that class.  */
  3488.       {
  3489.         register struct table_elt *elt = sets[i].src_elt;
  3490.  
  3491.         while (elt && elt->first_same_value == 0)
  3492.           elt = elt->next_same_value;
  3493.         sets[i].src_elt = elt ? elt->first_same_value : 0;
  3494.       }
  3495.       }
  3496.  
  3497.   /* Now insert the destinations into their equivalence classes.  */
  3498.  
  3499.   for (i = 0; i < n_sets; i++)
  3500.     if (sets[i].rtl)
  3501.       {
  3502.     register rtx dest = SET_DEST (sets[i].rtl);
  3503.     register struct table_elt *elt;
  3504.  
  3505.     if (flag_float_store
  3506.         && GET_CODE (dest) == MEM
  3507.         && (GET_MODE (dest) == SFmode || GET_MODE (dest) == DFmode))
  3508.       continue;
  3509.  
  3510.     /* STRICT_LOW_PART isn't part of the value BEING set,
  3511.        and neither is the SUBREG inside it.
  3512.        Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT.  */
  3513.     if (GET_CODE (dest) == STRICT_LOW_PART)
  3514.       dest = SUBREG_REG (XEXP (dest, 0));
  3515.  
  3516.     if (GET_CODE (dest) == REG)
  3517.       /* Registers must also be inserted into chains for quantities.  */
  3518.       if (insert_regs (dest, sets[i].src_elt, 1))
  3519.         /* If `insert_regs' changes something, the hash code must be
  3520.            recalculated.  */
  3521.         sets[i].dest_hash_code = HASHREG (dest);
  3522.  
  3523.     if (GET_CODE (dest) == SUBREG)
  3524.       /* Registers must also be inserted into chains for quantities.  */
  3525.       if (insert_regs (dest, sets[i].src_elt, 1))
  3526.         /* If `insert_regs' changes something, the hash code must be
  3527.            recalculated.  */
  3528.         sets[i].dest_hash_code
  3529.           = canon_hash (dest, GET_MODE (dest)) % NBUCKETS;
  3530.  
  3531.     elt = insert (dest, sets[i].src_elt, sets[i].dest_hash_code, GET_MODE (dest));
  3532.     elt->in_memory = GET_CODE (sets[i].inner_dest) == MEM;
  3533.     if (elt->in_memory)
  3534.       {
  3535.         elt->in_struct = (MEM_IN_STRUCT_P (sets[i].inner_dest)
  3536.                   || sets[i].inner_dest != SET_DEST (sets[i].rtl));
  3537.       }
  3538.       }
  3539.  
  3540.   /* Special handling for (set REG0 REG1)
  3541.      where REG0 is the "cheapest", cheaper than REG1.
  3542.      After cse, REG1 will probably not be used in the sequel, 
  3543.      so (if easily done) change this insn to (set REG1 REG0) and
  3544.      replace REG1 with REG0 in the previous insn that computed their value.
  3545.      Then REG1 will become a dead store and won't cloud the situation
  3546.      for later optimizations.  */
  3547.   if (n_sets == 1 && sets[0].rtl && GET_CODE (SET_DEST (sets[0].rtl)) == REG
  3548.       && GET_CODE (SET_SRC (sets[0].rtl)) == REG
  3549.       && rtx_equal_p (canon_reg (SET_SRC (sets[0].rtl)), SET_DEST (sets[0].rtl)))
  3550.     {
  3551.       rtx prev = PREV_INSN (insn);
  3552.       while (prev && GET_CODE (prev) == NOTE)
  3553.     prev = PREV_INSN (prev);
  3554.  
  3555.       if (prev && GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == SET
  3556.       && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl))
  3557.     {
  3558.       rtx dest = SET_DEST (sets[0].rtl);
  3559.       SET_DEST (PATTERN (prev)) = dest;
  3560.       SET_DEST (sets[0].rtl) = SET_SRC (sets[0].rtl);
  3561.       SET_SRC (sets[0].rtl) = dest;
  3562.     }
  3563.     }
  3564.  
  3565.   /* Did this insn become an unconditional branch or become a no-op?  */
  3566.   if (GET_CODE (insn) == JUMP_INSN
  3567.       && GET_CODE (x) == SET
  3568.       && SET_DEST (x) == pc_rtx)
  3569.     {
  3570.       if (SET_SRC (x) == pc_rtx)
  3571.     {
  3572.       PUT_CODE (insn, NOTE);
  3573.       NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
  3574.       NOTE_SOURCE_FILE (insn) = 0;
  3575.       cse_jumps_altered = 1;
  3576.       /* If previous insn just set CC0 for us, delete it too.  */
  3577.       if (prev_insn_cc0 != 0 || prev_insn_explicit_cc0 != 0)
  3578.         {
  3579.           PUT_CODE (prev_insn, NOTE);
  3580.           NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED;
  3581.           NOTE_SOURCE_FILE (prev_insn) = 0;
  3582.         }
  3583.       /* One less use of the label this insn used to jump to.  */
  3584.       --LABEL_NUSES (JUMP_LABEL (insn));
  3585.     }
  3586.       else if (GET_CODE (SET_SRC (x)) == LABEL_REF)
  3587.     {
  3588.       rtx label;
  3589.  
  3590.       emit_barrier_after (insn);
  3591.       cse_jumps_altered = 1;
  3592.       /* If previous insn just set CC0 for us, delete it too.  */
  3593.       if (prev_insn_cc0 != 0 || prev_insn_explicit_cc0 != 0)
  3594.         {
  3595.           PUT_CODE (prev_insn, NOTE);
  3596.           NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED;
  3597.           NOTE_SOURCE_FILE (prev_insn) = 0;
  3598.         }
  3599.       /* If jump target is the following label, and this is only use of it,
  3600.          skip direct to that label and continue optimizing there.  */
  3601.       label = insn;
  3602.       while (label != 0 && GET_CODE (label) != CODE_LABEL)
  3603.         label = NEXT_INSN (label);
  3604.       if (label == XEXP (SET_SRC (x), 0)
  3605.           && LABEL_NUSES (label) == 1)
  3606.         cse_skip_to_next_block = 1;
  3607.     }
  3608.     }
  3609.  
  3610.   /* If this insn used to store a value based on CC0 but now value is constant,
  3611.      and the previous insn just set CC0 for us, delete previous insn.
  3612.      Here we use the fact that nothing expects CC0 to be valid over an insn,
  3613.      which is true until the final pass.  */
  3614.   if (GET_CODE (x) == SET && prev_insn_cc0
  3615.       && CONSTANT_P (SET_SRC (x)))
  3616.     {
  3617.       PUT_CODE (prev_insn, NOTE);
  3618.       NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED;
  3619.       NOTE_SOURCE_FILE (prev_insn) = 0;
  3620.     }
  3621.  
  3622. #if defined ( DSP56000 ) || defined ( DSP96000 ) || defined ( DSP56100 )
  3623.   /* make sure the mangled insn matches. */
  3624.     { 
  3625.     enum rtx_code code = GET_CODE ( insn );
  3626.     
  3627.     if (( INSN == code || JUMP_INSN == code || CALL_INSN == code ) &&
  3628.         ( 0 > asm_noperands ( PATTERN ( insn ))))
  3629.     {
  3630.         INSN_CODE ( insn ) = -1;
  3631.         if ( -1 == recog_memoized ( insn ))
  3632.         {
  3633.         PATTERN ( insn ) = original_pattern;
  3634.         (void) recog_memoized ( insn );
  3635.         }
  3636.         INSN_CODE ( insn ) = -1;
  3637.     }
  3638.     }
  3639. #endif  
  3640.   prev_insn_explicit_cc0 = this_insn_explicit_cc0;
  3641.   prev_insn_cc0 = this_insn_cc0;
  3642.   prev_insn = insn;
  3643. }
  3644.  
  3645. /* Store 1 in *WRITES_PTR for those categories of memory ref
  3646.    that must be invalidated when the expression WRITTEN is stored in.
  3647.    If WRITTEN is null, say everything must be invalidated.  */
  3648.  
  3649. static void
  3650. note_mem_written (written, writes_ptr)
  3651.      rtx written;
  3652.      struct write_data *writes_ptr;
  3653. {
  3654.   static struct write_data everything = {1, 1, 1};
  3655.  
  3656.   if (written == 0)
  3657.     *writes_ptr = everything;
  3658.   else if (GET_CODE (written) == MEM)
  3659.     {
  3660.       /* Pushing or popping the stack invalidates nothing.  */
  3661.       rtx addr = XEXP (written, 0);
  3662.       if ((GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC
  3663.        || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC)
  3664.       && GET_CODE (XEXP (addr, 0)) == REG
  3665.       && REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
  3666.     return;
  3667.       if (GET_MODE (written) == BLKmode)
  3668.     *writes_ptr = everything;
  3669.       else if (cse_rtx_addr_varies_p (written))
  3670.     {
  3671.       /* A varying address that is a sum indicates an array element,
  3672.          and that's just as good as a structure element
  3673.          in implying that we need not invalidate scalar variables.  */
  3674.       if (!(MEM_IN_STRUCT_P (written)
  3675.         || GET_CODE (XEXP (written, 0)) == PLUS))
  3676.         writes_ptr->all = 1;
  3677.       writes_ptr->nonscalar = 1;
  3678.     }
  3679.       writes_ptr->var = 1;
  3680.     }
  3681. }
  3682.  
  3683. /* Perform invalidation on the basis of everything about an insn
  3684.    except for invalidating the actual places that are SET in it.
  3685.    This includes the places CLOBBERed, and anything that might
  3686.    alias with something that is SET or CLOBBERed.
  3687.  
  3688.    W points to the writes_memory for this insn, a struct write_data
  3689.    saying which kinds of memory references must be invalidated.
  3690.    X is the pattern of the insn.  */
  3691.  
  3692. static void
  3693. invalidate_from_clobbers (w, x)
  3694.      struct write_data *w;
  3695.      rtx x;
  3696. {
  3697.   /* If W->var is not set, W specifies no action.
  3698.      If W->all is set, this step gets all memory refs
  3699.      so they can be ignored in the rest of this function.  */
  3700.   if (w->var)
  3701.     invalidate_memory (w);
  3702.  
  3703.   if (GET_CODE (x) == CLOBBER)
  3704.     {
  3705.       rtx ref = XEXP (x, 0);
  3706.       if (ref
  3707.       && (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
  3708.           || (GET_CODE (ref) == MEM && ! w->all)))
  3709.     invalidate (ref);
  3710.     }
  3711.   else if (GET_CODE (x) == PARALLEL)
  3712.     {
  3713.       register int i;
  3714.       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
  3715.     {
  3716.       register rtx y = XVECEXP (x, 0, i);
  3717.       if (GET_CODE (y) == CLOBBER)
  3718.         {
  3719.           rtx ref = XEXP (y, 0);
  3720.           if (ref
  3721.           &&(GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
  3722.              || (GET_CODE (ref) == MEM && !w->all)))
  3723.         invalidate (ref);
  3724.         }
  3725.     }
  3726.     }
  3727. }
  3728.  
  3729. /* Find the end of INSN's basic block, and return the cuid of its last insn
  3730.    and the total number of SETs in all the insns of the block.  */
  3731.  
  3732. struct cse_basic_block_data { int cuid, nsets; rtx last; };
  3733.  
  3734. static struct cse_basic_block_data
  3735. cse_end_of_basic_block (insn)
  3736.      rtx insn;
  3737. {
  3738.   rtx p = insn;
  3739.   struct cse_basic_block_data val;
  3740.   int nsets = 0;
  3741.   int last_uid = 0;
  3742.  
  3743.   /* Scan to end of this basic block.  */
  3744.   while (p && GET_CODE (p) != CODE_LABEL)
  3745.     {
  3746.       /* Don't cse out the end of a loop.  This makes a difference
  3747.      only for the unusual loops that always execute at least once;
  3748.      all other loops have labels there so we will stop in any case.
  3749.      Cse'ing out the end of the loop is dangerous because it
  3750.      might cause an invariant expression inside the loop
  3751.      to be reused after the end of the loop.  This would make it
  3752.      hard to move the expression out of the loop in loop.c,
  3753.      especially if it is one of several equivalent expressions
  3754.      and loop.c would like to eliminate it.
  3755.      The occasional optimizations lost by this will all come back
  3756.      if loop and cse are made to work alternatingly.  */
  3757.       if (GET_CODE (p) == NOTE
  3758.       && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
  3759.     break;
  3760.  
  3761.       /* Don't cse over a call to setjmp; on some machines (eg vax)
  3762.      the regs restored by the longjmp come from
  3763.      a later time than the setjmp.  */
  3764.       if (GET_CODE (p) == NOTE
  3765.       && NOTE_LINE_NUMBER (p) == NOTE_INSN_SETJMP)
  3766.     break;
  3767.  
  3768.       /* A PARALLEL can have lots of SETs in it,
  3769.      especially if it is really an ASM_OPERANDS.  */
  3770.       if (GET_CODE (p) == INSN && GET_CODE (PATTERN (p)) == PARALLEL)
  3771.     nsets += XVECLEN (PATTERN (p), 0);
  3772.       else
  3773.     nsets += 1;
  3774.  
  3775.       last_uid = INSN_UID (p);
  3776.       p = NEXT_INSN (p);
  3777.     }
  3778.   val.cuid = uid_cuid[last_uid];
  3779.   val.nsets = nsets;
  3780.   val.last = p;
  3781.  
  3782.   return val;
  3783. }
  3784.  
  3785. static rtx cse_basic_block ();
  3786.  
  3787. /* Perform cse on the instructions of a function.
  3788.    F is the first instruction.
  3789.    NREGS is one plus the highest pseudo-reg number used in the instruction.
  3790.  
  3791.    Returns 1 if jump_optimize should be redone due to simplifications
  3792.    in conditional jump instructions.  */
  3793.  
  3794. int
  3795. cse_main (f, nregs)
  3796.      /* f is the first instruction of a chain of insns for one function */
  3797.      rtx f;
  3798.      /* nregs is the total number of registers used in it */
  3799.      int nregs;
  3800. {
  3801.   register rtx insn = f;
  3802.   register int i;
  3803.  
  3804.   cse_jumps_altered = 0;
  3805.  
  3806.   init_recog ();
  3807.  
  3808.   max_reg = nregs;
  3809.  
  3810.   all_minus_one = (int *) alloca (nregs * sizeof (int));
  3811.   consec_ints = (int *) alloca (nregs * sizeof (int));
  3812.   for (i = 0; i < nregs; i++)
  3813.     {
  3814.       all_minus_one[i] = -1;
  3815.       consec_ints[i] = i;
  3816.     }
  3817.  
  3818.   reg_next_eqv = (int *) alloca (nregs * sizeof (int));
  3819.   reg_prev_eqv = (int *) alloca (nregs * sizeof (int));
  3820.   reg_qty = (int *) alloca (nregs * sizeof (int));
  3821.   reg_rtx = (rtx *) alloca (nregs * sizeof (rtx));
  3822.   reg_in_table = (int *) alloca (nregs * sizeof (int));
  3823.   reg_tick = (int *) alloca (nregs * sizeof (int));
  3824.  
  3825.   /* Discard all the free elements of the previous function
  3826.      since they are allocated in the temporarily obstack.  */
  3827.   bzero (table, sizeof table);
  3828.   free_element_chain = 0;
  3829.   n_elements_made = 0;
  3830.  
  3831.   /* Find the largest uid.  */
  3832.  
  3833.   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
  3834.     if (INSN_UID (insn) > i)
  3835.       i = INSN_UID (insn);
  3836.  
  3837.   uid_cuid = (short *) alloca ((i + 1) * sizeof (short));
  3838.   bzero (uid_cuid, (i + 1) * sizeof (short));
  3839.  
  3840.   /* Compute the mapping from uids to cuids.
  3841.      CUIDs are numbers assigned to insns, like uids,
  3842.      except that cuids increase monotonically through the code.
  3843.      Don't assign cuids to line-number NOTEs, so that the distance in cuids
  3844.      between two insns is not affected by -g.  */
  3845.  
  3846.   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
  3847.     {
  3848.       if (GET_CODE (insn) != NOTE
  3849.       || NOTE_LINE_NUMBER (insn) < 0)
  3850.     INSN_CUID (insn) = ++i;
  3851.       else
  3852.     /* Give a line number note the same cuid as preceding insn.  */
  3853.     INSN_CUID (insn) = i;
  3854.     }
  3855.  
  3856.   /* Loop over basic blocks.
  3857.      Compute the maximum number of qty's needed for each basic block
  3858.      (which is 2 for each SET).  */
  3859.   insn = f;
  3860.   while (insn)
  3861.     {
  3862.       struct cse_basic_block_data val;
  3863.  
  3864.       val = cse_end_of_basic_block (insn);
  3865.  
  3866.       cse_basic_block_end = val.cuid;
  3867.       cse_basic_block_start = INSN_CUID (insn);
  3868.       max_qty = val.nsets * 2;
  3869.  
  3870.       /* Make MAX_QTY bigger to give us room to optimize
  3871.      past the end of this basic block, if that should prove useful.  */
  3872.       if (max_qty < 500)
  3873.     max_qty = 500;
  3874.  
  3875.       max_qty += max_reg;
  3876.  
  3877.       insn = cse_basic_block (insn, val.last);
  3878. #ifdef USE_C_ALLOCA
  3879.       alloca (0);
  3880. #endif
  3881.     }
  3882.  
  3883.   /* Tell refers_to_mem_p that qty_const info is not available.  */
  3884.   qty_const = 0;
  3885.  
  3886.   if (max_elements_made < n_elements_made)
  3887.     max_elements_made = n_elements_made;
  3888.  
  3889.   return cse_jumps_altered;
  3890. }
  3891.  
  3892. static rtx
  3893. cse_basic_block (from, to)
  3894.      register rtx from, to;
  3895. {
  3896.   register rtx insn;
  3897.   int *qv1 = (int *) alloca (max_qty * sizeof (int));
  3898.   int *qv2 = (int *) alloca (max_qty * sizeof (int));
  3899.   rtx *qv3 = (rtx *) alloca (max_qty * sizeof (rtx));
  3900.  
  3901.   qty_first_reg = qv1;
  3902.   qty_last_reg = qv2;
  3903.   qty_const = qv3;
  3904.   qty_const_insn = (rtx *) alloca (max_qty * sizeof (rtx));
  3905.  
  3906.   new_basic_block ();
  3907.  
  3908.   cse_skip_to_next_block = 0;
  3909.  
  3910.   for (insn = from; insn != to; insn = NEXT_INSN (insn))
  3911.     {
  3912.       register enum rtx_code code;
  3913.  
  3914.       code = GET_CODE (insn);
  3915.  
  3916.       if (code == INSN || code == JUMP_INSN || code == CALL_INSN)
  3917.     cse_insn (insn);
  3918.       /* Memory, and some registers, are invalidate by subroutine calls.  */
  3919.       if (code == CALL_INSN)
  3920.     {
  3921.       register int i;
  3922.       static struct write_data everything = {1, 1, 1};
  3923.       invalidate_memory (&everything);
  3924.       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
  3925.         if (call_used_regs[i] && reg_rtx[i]
  3926.         && i != FRAME_POINTER_REGNUM
  3927.         && i != ARG_POINTER_REGNUM)
  3928.           invalidate (reg_rtx[i]);
  3929.     }
  3930.       /* Loop beginnings are often followed by jumps
  3931.      (that enter the loop above the endtest).
  3932.      See if we can prove the loop will be executed at least once;
  3933.      if so, delete the jump.  Also perhaps we can prove loop
  3934.      will never be executed and delete the entire thing.  */
  3935.       if (code == NOTE
  3936.       && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
  3937.       && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN)
  3938.     {
  3939.       predecide_loop_entry (insn);
  3940.       /* Whether that jump was deleted or not,
  3941.          it certainly is the end of the basic block.
  3942.          Since the jump is unconditional,
  3943.          it requires no further processing here.  */
  3944.       break;
  3945.     }
  3946.  
  3947.       /* See if it is ok to keep on going past the label
  3948.      which used to end our basic block.  */
  3949.       if (cse_skip_to_next_block
  3950.       || (to != 0 && NEXT_INSN (insn) == to && LABEL_NUSES (to) == 0))
  3951.     {
  3952.       struct cse_basic_block_data val;
  3953.  
  3954.       /* Skip the remaining insns in this block.  */
  3955.       cse_skip_to_next_block = 0;
  3956.       insn = to;
  3957.       if (insn == 0)
  3958.         break;
  3959.  
  3960.       /* Find the end of the following block.  */
  3961.       val = cse_end_of_basic_block (NEXT_INSN (insn));
  3962.  
  3963.       /* If the tables we allocated have enough space left
  3964.          to handle all the SETs in the next basic block,
  3965.          continue through it.  Otherwise, return,
  3966.          and that block will be scanned individually.  */
  3967.       if (val.nsets * 2 + next_qty > max_qty)
  3968.         break;
  3969.  
  3970.       cse_basic_block_end = val.cuid;
  3971.       to = val.last;
  3972.     }
  3973.     }
  3974.  
  3975.   if (next_qty > max_qty)
  3976.     abort ();
  3977.  
  3978.   return to ? NEXT_INSN (to) : 0;
  3979. }
  3980.